题解 | #请客吃饭#

二分答案+滑动窗口

我们来看看为什么可以想出这个思路

首先我们假设所有的人都是数轴上的点，他们的坐标就是 a ，权值就是 b

对于一个隔阂值 m ，代表在数轴上选择一段长度为 m 的区间，区间里点的权值和就是贡献

那么这个区间就是滑动窗口，他的右端点一定在一个点上，因为从贪心的角度来看，如果右端点不在一个点上，那么我们可以把右端点向左移动，这样就可能会覆盖其他点，权值和就可能会增加

我们可以遍历维护出这个窗口，每次向右滑动到一个新的点，这时窗口中已经存在的点可能会离开窗口，但是一定是最左边的点离开，所以我们可以用一个双端队列来维护，同时记录最大的权值和，如果大于等于 k ，代表这个 m 是合法的

然后我们发现 m 是单调的，假设最终的答案是 M ，那么对于任意的 m >= M ，其权值和都是大于等于 k 的，也都是合法的，对于任意的 m < M ，其权值和都是小于 k 的，也都是不合法的，所以我们可以二分答案

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int __t = 1, n, k, a, b;
vector<pair<int, int>> v;
int ck(int m) {
    deque<pair<int, int>> q;
    int sum = 0, ma = 0;
    for (auto [a, b] : v) {
        q.push_back({a, b}), sum += b;
        while (!q.empty() && q.front().first < a - m)
            sum -= q.front().second, q.pop_front();
        ma = max(ma, sum);
    }
    return ma >= k;
}
void solve() {
    cin >> n >> k;
    v.resize(n);
    for (int i = 0; i < n; i++)
        cin >> v[i].first;
    for (int i = 0; i < n; i++)
        cin >> v[i].second;
    sort(v.begin(), v.end());
    int l = 0, r = 1e9;
    while (l < r) {
        int m = (l + r) / 2;
        if (ck(m))
            r = m;
        else
            l = m + 1;
    }
    cout << (l == 1e9 ? -1 : l) << '\n';
    return;
}
int32_t main() {
#ifdef ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    // cin >> __t;
    while (__t--)
        solve();
    return 0;
}