3531
42
Link bài:
Thuật toán:
Code:
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[i];
for (int i = 1; i < n; i++){
k = a[i];
ans = doit(i+1, n);
if (ans) {cout << a[i] << " " << ans; break;}
}
if (!ans) cout << -1;
return 0;
}
