【z05】聪明的质检员

【题目链接】:http://noi.qz5z.com/viewtask.asp?id=z05

【题解】

显然w越大，最后的Y也就越大;
可以依靠这个搞二分；
如果二分枚举的tw得到的Y比S小,则减小tw以增大Y,否则增大tw就好;
那个区间的和可以用前缀和搞出来(确定当前的tw然后搞前缀和)；
枚举一下m个区间,每个区间都能O（1）搞出来则m个区间为O(m);然后前缀和搞一下是O(n);
然后二分w为O(logw);
总的复杂度为O(logw*(n+m))；
完全可以接受了;

【完整代码】

#include <algorithm>
#include <cstdio>
#define LL long long

using namespace std;

const int MAXN = 2e5+100;
const LL INF = 1e18;

int sum[MAXN];
LL w[MAXN],v[MAXN];
LL sumv[MAXN];

int n,m,query[MAXN][2];
LL s,ans = INF;

LL jue(LL x)
{
    if (x>=0)
        return x;
    else
        return -x;
}

int main()
{
    //freopen("F:\rush.txt","r",stdin);
    scanf("%d%d%I64d",&n,&m,&s);
    for (int i = 1;i <= n;i++)
        scanf("%I64d%I64d",&w[i],&v[i]);
    for (int i = 1;i <= m;i++)
        scanf("%d%d",&query[i][0],&query[i][1]);
    int l = 0,r = 1000000;
    while (l <= r)
    {
        int tw = (l+r)>>1;
        sum[0] = 0;sumv[0] = 0;
        for (int i = 1;i <= n;i++)
            if (w[i]>=tw)
                sum[i] = sum[i-1]+1,sumv[i] = sumv[i-1]+v[i];
            else
                sum[i] = sum[i-1],sumv[i] = sumv[i-1];
        LL temp = 0;
        for (int i = 1;i <= m;i++)
        {
            LL tem1 = sum[query[i][1]]-sum[query[i][0]-1];
            LL tem2 = sumv[query[i][1]]-sumv[query[i][0]-1];
            temp += tem1*tem2;
        }
        ans = min(ans,jue(temp-s));
        if (temp >s)
            l = tw+1;
        else
            r = tw-1;
    }
    printf("%I64d
",ans);
    return 0;
}