题解 | #请客吃饭#

二分答案，check的时候枚举每一个然后二分找一段连续的区间即可。

#include<bits/stdc++.h>
#define int long long
#define double long double
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 3e5 + 10;
const int M = 1e3 + 10;
int mod = 1e9 + 7;
struct Link {
    int a, b;
} s[N];
int a1[N], b1[N];
bool cmp(Link xx, Link yy) {
    return xx.a < yy.a;
}

void solve() {
    int n;
    cin >> n;
    int sum = 0;
    int k;
    cin >> k;
    for (int i = 1; i <= n; i++) cin >> s[i].a;
    for (int i = 1; i <= n; i++) cin >> s[i].b, sum += s[i].b;
    if (sum < k) {
        cout << "-1\n";
        return ;
    }
    sort(s + 1, s + n + 1, cmp);
    for (int i = 1; i <= n; i++) {
        a1[i] = s[i].a;
        b1[i] = s[i].b;
        b1[i] += b1[i - 1];
    }
    int l = 1, r = 1e10;
    while (l <= r) {
        int mid = (l + r) / 2;
        int flag = 0;
        // cout<<mid<<"\n";
        for (int i = 1; i <= n; i++) {
            int k2 = upper_bound(a1 + 1, a1 + n + 1, a1[i] + mid) - a1 - 1;
            if (i <= k2 && b1[k2] - b1[i - 1] >= k) {
                flag++;
                break;
            }
        }
        if (flag) r = mid - 1;
        else l = mid + 1;
    }
    cout << l << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int _;
    _ = 1;
    //cin>>_;
    while (_--) {
        solve();
    }
}