AcWing 499. 聪明的质监员

AcWing 499. 聪明的质监员

二分，注意一下怎么确定数据范围，使用long long

Y随W增大而减小，具有单调性

#include<bits/stdc++.h>

using namespace std;

const int N = 200010;
typedef long long LL;
int w[N], v[N], L[N], R[N];
LL sum[N], cnt[N];
int n, m;
LL S;

LL get_y(int W) {
    LL res = 0;
    for (int i = 1; i <= n; i++) {
        if (w[i] >= W) {
            sum[i] = sum[i - 1] + v[i];
            cnt[i] = cnt[i - 1] + 1;
        } else {
            sum[i] = sum[i - 1];
            cnt[i] = cnt[i - 1];
        }
    }
    for (int i = 1; i <= m; i++) {
        res += (sum[R[i]] - sum[L[i] - 1]) * (cnt[R[i]] - cnt[L[i] - 1]);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> m >> S;
    for (int i = 1; i <= n; i++)cin >> w[i] >> v[i];
    for (int i = 1; i <= m; i++)cin >> L[i] >> R[i];

    int l = 0, r = 1e6+10;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        LL Y = get_y(mid);
        if (Y >= S)l = mid;
        else r = mid - 1;
    }

    cout << min(get_y(r) - S, S- get_y(r + 1));

}