「NOIP2011 Day2 T2」聪明的质监员 (二分+前缀和)

题意见上。

只能二分$W$了。
当前二分的是$W$,那么用前缀和算出当前的$Y$,和$S$比较,大的话就将$W$增加,否则减小。

知识点:
二分,前缀和技巧

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<string>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const LL MAXN = 200000 + 5;

    LL n, m, S, v[MAXN], w[MAXN], L[MAXN], R[MAXN];
    LL qzh_v[MAXN], qzh_gs[MAXN];

    LL abss(LL x) {return x > 0 ? x : -x;}

    LL chk(LL x) {
        ms(qzh_v, 0), ms(qzh_gs, 0);
        for (LL i = 1; i <= n; ++i) if (w[i] >= x) {
            qzh_v[i] += v[i], qzh_gs[i]++;
        }
        for (LL i = 1; i <= n; ++i)
            qzh_v[i] += qzh_v[i - 1], qzh_gs[i] += qzh_gs[i - 1];
        LL ret = 0;
        for (LL i = 1; i <= m; ++i) {
            LL val = (qzh_v[R[i]] - qzh_v[L[i] - 1]) * (qzh_gs[R[i]] - qzh_gs[L[i] - 1]);
            ret += val;
        }
        return ret;
    }

    void clean() {
    }
    int solve() {

        clean(); 
        cin >> n >> m >> S;
        for (LL i = 1; i <= n; ++i) {
            scanf("%lld%lld", &w[i], &v[i]);
        }
        for (LL i = 1; i <= m; ++i) {
            scanf("%lld%lld", &L[i], &R[i]);
        }

        LL l = 0ll, r = 1e13, ans = 1e13;
        while (l < r) {
            LL mid = (l + r) >> 1;
            LL tmp = chk(mid);
            if (tmp > S) l = mid + 1, ans = min(ans, abss(tmp - S)); else r = mid, ans = min(ans, abss(tmp - S));
        }

        printf("%lld\n", ans);

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
/*
*/
------ 本文结束 ------