[ABC364D] K-th Nearest
很好想的题目。
首先可以考虑到答案具有单调性，所以对于每一次询问用二分处理即可。
然后考虑如何判合法。我们需要找到所有 \(a_i-b\) 中 \(\le x\) 且 \(\ge -x\) 的个数。可以现将 \(a_i\) 排好序，最后用两个二分统计个数看是否 \(\ge k\) 即可。
时间复杂度 \(O(q \log^2 n)\)。
点击查看代码
```cpp #includeusing namespace std;
const int N = 2e5 + 10;
int n, q, a[N], k, b;
bool check(int x) {
int L = n+1, R = 0;
int l = 1, r = n;
while(l <= r) {
int mid = l + r >> 1;
if(a[mid] - b <= x) {
R = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
l = 1, r = n;
while(l <= r) {
int mid = l + r >> 1;
if(a[mid] - b >= -x) {
L = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return (R-L+1) >= k;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> q;
For(i,1,n) cin >> a[i];
sort(a + 1, a + n + 1);
while(q--) {
int l = 0, r = 2e8, ans = 0;
cin >> b >> k;
while(l <= r) {
int mid = l + r >> 1;
if(check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
cout << ans << '\n';
}
return 0;
}
</details>