Giải bài ntucoder DIKI - Sân điền kinh

Link bài:

Thuật toán:

• Ta sắp xếp các vạch sơn theo thứ tự tăng dần của khoảng các tới đầu sân.
  
• Dùng chặt nhị phân để giảm độ phức tạp khi tìm kiếm vạch chạy xuống O (logn).
  
• Với vạch sân thứ i, ta sẽ tìm kiếm trên đoạn i+1 → n. Do đoạn 1→ i-1 đã được tìm kiếm trước đó.

Code:

Mã:

#include <bits/stdc++.h>
using namespace std;

int k, n, m, ans;
int a[100007];

int doit(int l, int r){
    if (l > r) return 0;
    if (l == r){
        if (a[l] - k == m) return a[l];
        return 0;
    }
    if (a[l] > k+m) return 0;
    if (a[r] < k+m) return 0;
    int mid = (l+r)/2;
    if (a[mid] - k == m) return a[mid];
    return max(doit(l, mid), doit(mid+1, r));
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("diki.inp", "r", stdin);
    //freopen("diki.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a;
    for (int i = 1; i < n; i++){
        k = a;
        ans = doit(i+1, n);
        if (ans) {cout << a << " " << ans; break;}
    }
    if (!ans) cout << -1;
    
    return 0;
}