题解 P1314 【聪明的质监员】

· · 题解

这题需要俩个技巧。一个是二分答案。显然我们无法直接算出W的值，只能枚举W，比较Y与S的大小，然后缩减枚举范围。O(logn)

另一个就是前缀和。因为区间很多，而且区间范围也很大，我们必须在O(n)的时间计算每个W得到的Y，所以我们先O(n)预处理出所有sum[i]=1.....i的的校验值，然后要求【l[i],r[i]】,只需：sum[r[i]]-sum[l[i]-1]

一审没给过？解释少了？？？那我在啰嗦一下吧。

问题中Y会随W的增大而减小，具有单调性，所以可以二分答案。

二分的题目通常会有死的模板，经常一些就死循环，或者答案就是差1多1什么的童鞋，可以看看我的博客：http://blog.csdn.net/no1\_terminator/article/details/52957467

里面归纳了一下一些常见的模型，应该会有帮助

参考代码：

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=200100;
LL ans=0x3f3f3f3f3f3f3f3f;
LL sw[N],sv[N],w[N],v[N];
int l[N],r[N];
int n,m;
LL S;
LL f(LL a,LL b){
    return a>b?a-b:b-a;
}
bool check(LL mid){
    for (int i=1;i<=n;i++){
        sw[i]=sw[i-1]+(w[i]>=mid);
        sv[i]=sv[i-1]+(w[i]>=mid)*v[i];
    }
    LL W=0;
    for (int i=1;i<=m;i++){
        W+=(sw[r[i]]-sw[l[i]-1])*(sv[r[i]]-sv[l[i]-1]);
    }
    ans=min(ans,f(W,S));
    return W<=S;
}
int main(){
    scanf("%d%d%lld",&n,&m,&S);
    LL Left=0,Right=0;
    for (int i=1;i<=n;i++){
        scanf("%lld%lld",&w[i],&v[i]);
        Right=max(Right,w[i]);
    }
    Right++;
    for (int i=1;i<=m;i++){
        scanf("%d%d",&l[i],&r[i]);
    }
    while (Left+1<Right){
        int mid=(Left+Right)>>1;
        if (check(mid))Right=mid;
            else Left=mid;
    }
    check(Left);check(Right);
    printf("%lld",ans);
    return 0;
}