题解 | #请客吃饭#

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node{
    int a = 0, b = 0;
}fri[200005];
int h[200005];
bool cmp(node a, node b){
    return a.a <= b.a;
}
signed main() {
    int n, k, sum = 0;
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> fri[i].a;
    }
    for(int i = 1; i <= n; i++){
        cin >> fri[i].b;
        sum += fri[i].b;
    }
    if(sum < k){
        cout << -1;
        return 0;
    }
    sort(fri, fri + n + 1, cmp);
    for(int i = 1; i <= n; i++){
        h[i] += h[i-1];
        h[i] += fri[i].b;
        //cout << h[i];
    }
    //cout << endl;
    //cout << fri[0].b << fri[1].b << fri[2].b << fri[3].b << endl;
    //cout << fri[0].a << fri[1].a << fri[2].a << fri[3].a << endl;
    int l = 0, r = 1, minn = 999999999;
    for(int i = 1; i <= n; i++){
        r = i;
        //cout << h[i] - h[l] << endl;
        if((h[r] - h[l]) < k){
            ///什么也不做
            //cout << 1 << l << r << endl;
        }
        else{
            while((h[r] - h[l]) >= k){
                l++;
            }
            //if((h[r] - h[l]) < k) l--;
            //cout << 2 << l << r << h[r] - h[l]  <<  fri[r].a - fri[l].a<< endl;
            minn = min(minn, fri[r].a - fri[l].a);
        }
    }
    cout << minn << endl;

}
// 64 位输出请用 printf("%lld")

不需要二分, 直接滑动窗口滑一遍

首先按照财富值排序, 这样方便计算隔阂

然后对于每一个l先滑到合适的r, 进行计算.

随后l++, 然后来更新r(似乎直接更新r和l也没关系, 但是总之代码跑起来了)