思路:首先二分需要数列有二分性,我们要对数列排序,然后二分距离,直到出现一个距离可以满足,点数大于等于k。
代码:
void solve(){int n, q;cin >> n >> q;vector<int>a(n);for(int i = 0;i < n;i ++)cin >> a[i];sort(a.begin(),a.end());while(q --){int x, k;cin >> x >> k;int l = -1, r = 2e9 + 10;while(l + 1 < r){int mid = l + r >> 1;int fl = lower_bound(a.begin(),a.end(), x - mid) - a.begin();int fr = upper_bound(a.begin(),a.end(), x + mid) - a.begin();if(fr - fl >= k) // [fl,fr)r = mid;elsel = mid;}cout << r << endl;}
}