ĐƯỜNG ĐI BỘ

Xem dạng PDF
Gửi bài giải
Điểm: 100,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout
Dạng bài
Ngôn ngữ cho phép
C++, Pascal, Python

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 2
    notmerblx2123   đã bình luận 20 giờ trước ← chỉnh sửa

    C++ 20/20:

    Thuat toan su dung: binary search, Two Pointers va Min/max

    Copy
    #include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int w,h,n;
    if(!(cin>>w>>h>>n))return 0;
    vector<pii>a(n);
    for(int i=0;i&lt;n;i++){
        cin>>a[i].first>>a[i].second;
    }
    sort(a.begin(),a.end()); 


    vector<int> preMin(n+1, INT_MAX), preMax(n+1, INT_MIN);
    vector<int> sufMin(n+1, INT_MAX), sufMax(n+1, INT_MIN);
    for(int i=0;i&lt;n;i++){
        preMin[i+1]=min(preMin[i], a[i].second);
        preMax[i+1]=max(preMax[i], a[i].second);
    }
    for(int i=n-1;i>=0;i--){
        sufMin[i]=min(sufMin[i+1], a[i].second);
        sufMax[i]=max(sufMax[i+1], a[i].second);
    }

    auto ok = [&](int k)->bool{
        int r=0;
        for(int l=0;l&lt;n;l++){
            while(r&lt;n && a[r].first <= a[l].first + k - 1) r++;

            int mn = min(preMin[l], sufMin[r]);
            int mx = max(preMax[l], sufMax[r]);
            if(mn==INT_MAX || mx-mn+1 <= k) return true;
        }
        return false;
    };

    int lo=1, hi=max(w,h), ans=hi;
    while(lo<=hi){
        int mid=(lo+hi)>>1;
        if(ok(mid)){
            ans=mid;
            hi=mid-1;
        }else lo=mid+1;
    }
    cout<&lt;ans<<"\n";
    return 0;
}

// tham khao thoi nhe :)

  • 2
    minhlam14_bobi   đã bình luận một tháng trước

    sao bài này ko làm scratch đc nhể


  • 2
    Tama   đã bình luận một tháng trước ← chỉnh sửa

    Bài này giải bằng tìm kiếm nhị phân trên đáp án kết hợp kiểm tra bằng sliding window, lưu ô đặc biệt vào row,col. Sau đó duyệt cửa sổ kiểm tra bao phủ của từng ô đặc biệt. ( Tui dùng python nên sẽ để set lấy giá trị từ row và col để tránh trùng giá trị ).

    -Tái bút: Vừa sửa lại, dùng mảng cộng dồn 2 chiều lưu ô đặc biệt sẽ tối ưu hơn nha.


  • 1
    KVMB23A_67   đã bình luận lúc 1, Tháng 8, 2024, 16:30

    AC rồi!!!!!!!!!!!!!!!!!!!!!!!!!!!!


    • -1
      Nglinh_2k14   đã bình luận 2 tháng trước

      chi tui vs


    • -4
      sb20240044   đã bình luận 3 tháng trước

      cho mn bài bạn ơi :(((


      • 4
        KVMB23A_67   đã bình luận 3 tháng trước

        Cho thuật chứ ko cho bài:

        Sử dụng binary search để kiểm tra từng độ rộng xem có phù hợp ko, nếu phù hợp thì giảm còn ko thì tăng


        • 1
          sds   đã bình luận 4 ngày trước

          cảm ơn bro,cuối cùng tui cũng dc 5/20 test rồi:))


        • -1
          truongphat   đã bình luận một tháng trước

          đúng là top 1 có khác =))


        • 0
          maiducninh   đã bình luận 3 tháng trước

          Bạn biết làm code scratch ko ? Cho mình tham khảo với


          • 1
            Pham_Hoang_Nam   đã bình luận 10 ngày trước

            ngôn ngữ cho phép ko có scratch


  • 0
    KVMB23A_67   đã bình luận lúc 1, Tháng 8, 2024, 15:07

    khó quá


  • 1
    quan2013   đã bình luận lúc 21, Tháng 7, 2024, 21:38

    HELP ME


  • 0
    quan2013   đã bình luận lúc 21, Tháng 7, 2024, 21:38

    define


  • 0
    DucKien2014   đã bình luận lúc 28, Tháng 6, 2024, 21:55

    Help meee


  • -26
    duybaothcq   đã bình luận lúc 5, Tháng 5, 2024, 9:13

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.