算法

(二分答案+前缀和) $O((m+n)*log(maxW))$

由于我们并不清楚要求的$W$的值，但是我们知道$W$的值不超过矿石中价值最大的，如果$W$大于了矿石中价值最大的，那么$Y$的值为$0$，无法达到最优解。因此，很容易就能想到在确定$W$的值要用二分的方法。

在分析这道题的时候，我们很容易知道$Y$的值是满足单调性的，当$W$的值越大，$Y$的值越小，因为$W$越大，能够选的矿石就越少。所以我们把得到的$Y$值作为判断条件，如果$Y$比$S$小，就说明检验值小了，而$W$取大了。每次更改W的同时给$ans$取最小值。

那么$Y$又应该怎么求出呢？题目中$n$，$m$最大有2*10^5，
如果暴搜肯定超时，因此我们需要在枚举W的时候预处理。遍历w数组，保存满足条件的v和个数的前缀和。然后再遍历一遍要求的区间。
即$sum+=(cnt[R[i]]-cnt[L[i]-1]) \* ( sumv[R[i]] - sumv[L[i]])$
总的时间复杂度就从O(mnlog(maxW)) 变成了O((m+n)*log(maxW))。

C++ 代码

#include <iostream>
#include <cmath>
#define int long long

using namespace std;

const int N = 2e5 + 10, inf = 1ll << 60;

int n, m, mx;
int s, res = inf;
int l[N], r[N], w[N], v[N], sum[N], cnt[N];

int cal(int W) {
    int tmp = 0;
    for (int i = 1; i <= n; ++i) {
        sum[i] = sum[i - 1];
        cnt[i] = cnt[i - 1];
        if (w[i] >= W) {
            sum[i] += v[i];
            cnt[i]++;
        }
    }
    for (int i = 1; i <= m; ++i) {
        tmp += (cnt[r[i]] - cnt[l[i] - 1]) * (sum[r[i]] - sum[l[i] - 1]);
    }
    return tmp;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> s;
    for (int i = 1; i <= n; cin >> w[i] >> v[i], ++i);
    for (int i = 1; i <= n; ++i) mx = max(mx, w[i]);
    for (int i = 1; i <= m; cin >> l[i] >> r[i], ++i);

    int l = 0, r = mx + 1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        int need = cal(mid);
        res = min(res, abs(need - s));
        if (need < s) r = mid - 1;
        else l = mid + 1;
    }

    cout << res << '\n';

    return 0;
}