题解 P1314 【聪明的质监员】

pupuvovovovovo · 2017-05-01 21:42:24 · 题解

这题二分。

二分W，使得ans（即W）让Y（程序中是tot）最大且小于s。之后，比较W-1与W的值谁更接近s，打出即可。

judge函数中用了前缀和优化。

#include<bits/stdc++.h>
using namespace std;
int w[200001],v[200001],l[200001],r[200001],n,m,i,L,R,MID,ANS;
long long num[200001],sum[200001],s,tot,a,b;//longlong的变量名不要搞错，tot就是Y。
bool judge(int W){
    memset(num,0,sizeof(num));
    memset(sum,0,sizeof(sum));
    for (i=1;i<=n;i++){
        sum[i]=sum[i-1],num[i]=num[i-1];
        if (w[i]>=W){
            sum[i]+=v[i];//sum指这些大于W的数的和
            num[i]++;//num指有几个数大于W
        }
    }
    tot=0;
    for (i=1;i<=m;i++) tot+=(sum[r[i]]-sum[l[i]-1])*(num[r[i]]-num[l[i]-1]);//暴算
    if (tot<=s) return true;
    else return false;
}
int main(){
    scanf("%d%d%lld",&n,&m,&s);
    for (i=1;i<=n;i++) scanf("%d%d",&w[i],&v[i]);
    for (i=1;i<=m;i++) scanf("%d%d",&l[i],&r[i]);
    L=0;R=1000000;
    while (L<=R){
        MID=(L+R)/2;
        if (judge(MID)){
            R=MID-1;
            ANS=MID;
        }
        else L=MID+1;
    }
    L=judge(ANS);
    a=tot;
    R=judge(ANS-1);
    b=tot;
    printf("%lld",min(s-a,b-s));
    return 0;
}
P.S.：如果你去算复杂度，你会发现O（nlog1000000）约为4000,0000，再加上常数略麻烦，然而lg神机150ms。