题解 P1314 【聪明的质监员】

· · 题解

聪明的质监员

Solution

　　二分一个W含义如题意所示, 有一个重要的性质是W越大Y就越小, 根据这个调整W的范围．

　　根据这来调整W.计算Y时需要先算出满足\sum\left[w_j>W\right]w_j,\sum\left[w_j>W\right]1的前缀和, 暴力算当然不行. 　　 　　还要注意就是 long long 和 二分的范围[\text{1,r}]要足够, 要注意\text{while(l}\leq \text{r)}.

Code

#include<cstdio>
#define inf 999999999999//inf值要设的足够大
#define N 200005
#define int long long//后面所有的int都其实是long long
int ans;
int n,m,s;
int aaaa[N];
int sigma[N];
int v[N],w[N];
int le[N],ri[N];

inline int abs(int s){
    return s>0?s:-s;
}
inline int min(int a,int b){
    return a<b?a:b;
}

bool check(int W){
    sigma[0]=0;//sigma为满足w_j>W的w_j的前缀和
    aaaa[0]=0;//aaaa为满足w_j>W的数量的前缀和, 分别对应题目中两个sigma
    int an=0;//二分的W所对应的答案
    for(int i=1;i<=n;++i){
        sigma[i]=sigma[i-1];
        aaaa[i]=aaaa[i-1];
        if(w[i]>=W)sigma[i]+=v[i],++aaaa[i];//维护前缀和
    }
    for(int i=1;i<=m;++i)
        an+=(sigma[ri[i]]-sigma[le[i]-1])*(aaaa[ri[i]]-aaaa[le[i]-1]);//这是一段区间对于答案的贡献
    an=an-s;
    ans=min(abs(an),ans);
    return an>0;//如果答案>S说明答案在小一点(W变大)可能其减去S的绝对值更小
}

main(){
    ans=inf;//一开始给ans设一个较大的初值
    scanf("%lld%lld%lld",&n,&m,&s);
    for(int i=1;i<=n;++i)
        scanf("%lld%lld",&w[i],&v[i]);
    for(int i=1;i<=m;++i)
        scanf("%lld%lld",&le[i],&ri[i]);
    int l=0ll,r=inf,mid;//看到题解中有人用1-s作为二分范围, 需要足够大
    while(l<=r){//l<=r要格外注意
        mid=(l+r)>>1;
        if(check(mid))l=mid+1ll;
        else r=mid-1;
    }
    printf("%lld",ans);
    return 0;
}