NOIP 2011 聪明的质检员

容易知道Y(W)是关于随W的增大而递减的，因此可以想到用二分W使得Y逐步逼近S，由于题目要求绝对值最小，因此比较保险的方法是使用两次二分，分别求出恰好大于S的Y值和恰好小于S的Y值，然后输出距离S最近的即可。

然而，即使使用了二分，程序依然不能通过所有数据。因为我们忘了题目中的一个条件——区间总数上限是200000，而不同区间可能重合或相互重叠，所以，如果我们仅仅按照题目描述的方式计算每个区间上的Yi，那么在最坏情况仅仅计算所有区间上的Y就会超时，因此，需要一个更巧妙的方法——前缀和，实现方式请看代码。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MXN 200000+1

long cnt[MXN];
unsigned long long sum[MXN],s;
long w[MXN],v[MXN];
long m,n;
long range_l[MXN],range_r[MXN];

long long calc_range(long l,long r)
{
    return (cnt[r] - cnt[l - 1]) * (sum[r] - sum[l - 1]);
}

long long calc_tot(long lim)
{
    long long res = 0;
    long i;
        //空间换时间
    cnt[0] = 0;
    sum[0] = 0;
    for(i = 1;i <= n;i ++)
    {
        cnt[i] = cnt[i - 1];
        sum[i] = sum[i - 1];
        if(w[i] >= lim)
        {cnt[i] += 1;sum[i] += v[i];}
    }
    for(i = 0;i < m;i ++)
        res += calc_range(range_l[i],range_r[i]);
    return res;
}

int main()
{
    long i;
    long long a,b;
    scanf("%ld%ld%lld",&n,&m,&s);
    for(i = 1;i <= n;i ++)
        scanf("%ld%ld",&w[i],&v[i]);
    for(i = 0;i < m;i ++)
        scanf("%ld%ld",&range_l[i],&range_r[i]);

    long l,r,mid;
        //分别从两个方向逼近S
    l = 0;r = 10e6 + 1;
    while(l < r)
    {
        mid = (l + r) / 2;
        if(calc_tot(mid) <= s)
            r = mid;
        else
            l = mid + 1;
    }
    a = llabs(calc_tot(l) - s);

    l = 0;r = 10e6 + 1;
        //其实这里的l，r没有必要开这么大，读者可以自行分析
    while(l < r)
    {
        mid = (l + r + 1) / 2;
        if(calc_tot(mid) >= s)
            l = mid;
        else r = mid - 1;
    }
    b = llabs(calc_tot(l) - s);

    if(a < b)    printf("%lld\n",a);
    else printf("%lld\n",b);
    return 0;
}