P1314 聪明的质监员

题面:https://www.luogu.org/problem/P1314

本题直接二分W,当Y>s,那么增加W来减小Y,当Y<s,那么减小W来增大Y.
然后check的时候用前缀和优化即可.

Code:
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=200005;
int n,m,w[N],v[N],l[N],r[N];
long long sumn[N],sumv[N],Y,s,sum,ans=1e16;
bool check(int W){
    Y=0,sum=0;
    memset(sumn,0,sizeof(sumn));
    memset(sumv,0,sizeof(sumv));
    for(int i=1;i<=n;i++){
        if(w[i]>=W){
            sumn[i]=sumn[i-1]+1;
            sumv[i]=sumv[i-1]+v[i];
        }
        else{c 
            sumn[i]=sumn[i-1];
            sumv[i]=sumv[i-1];
        }
    }
    for(int i=1;i<=m;i++){
        Y+=(sumn[r[i]]-sumn[l[i]-1])*(sumv[r[i]]-sumv[l[i]-1]);
    }
    sum=abs(Y-s);
    if(Y>s){
        return 1;
    }
    else{
        return 0;
    }
}
int main(){
    scanf("%d%d%lld",&n,&m,&s); 
    for(int i=1;i<=n;i++){
        scanf("%d%d",&w[i],&v[i]);
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d",&l[i],&r[i]);
    }
    int l=1,r=1e6;
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid)){
            l=mid+1;
        }
        else{
            r=mid-1;
        }
        ans=min(sum,ans);
    }
    printf("%lld\n",ans);
    return 0;
}

P1314 聪明的质监员

原文：https://www.cnblogs.com/ukcxrtjr/p/11607385.html