P1314 聪明的质监员（前缀和+二分）

P1314 聪明的质监员

显然可以二分参数W

统计Y用下前缀和即可。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cctype>

 #include<algorithm>

 #include<cmath>

 #define re register

 using namespace std;

 typedef long long ll;

 void read(int &x){

     char c=getchar();x=;

     while(!isdigit(c)) c=getchar();

     while(isdigit(c)) x=(x<<)+(x<<)+(c^),c=getchar();

 }

 ll min(ll a,ll b){return a<b?a:b;}

 #define N 200002

 int n,m,w[N],v[N],tl[N],tr[N],c[N];

 ll s,sum1[N],sum2[N],ans=1e17;

 ll check(int lim){

     for(re int i=;i<=n;++i){

         if(w[i]<lim){

             sum1[i]=sum1[i-];

             sum2[i]=sum2[i-];

         }else{

             sum1[i]=sum1[i-]+v[i];//存权值和

             sum2[i]=sum2[i-]+;//存个数

         }

     }ll res=;

     for(re int i=;i<=m;++i){

         ll r1=sum1[tr[i]]-sum1[tl[i]-];

         ll r2=sum2[tr[i]]-sum2[tl[i]-];

         res+=r1*r2;//累加Y值

     }ans=min(ans,abs(res-s));

     return res;

 }

 int main(){

     read(n);read(m);scanf("%lld",&s);

     for(re int i=;i<=n;++i) read(w[i]),read(v[i]),c[i]=w[i];

     for(re int i=;i<=m;++i) read(tl[i]),read(tr[i]);

     sort(c+,c+n+);//重量值从小到大排序，用于二分

     int l=,r=n;

     while(l<r){

         int mid=l+((r-l)>>);

         if(check(c[mid])>s) l=mid+;//二分离s更近

         else r=mid;

     }printf("%lld",ans);

     return ;

 }

P1314 聪明的质监员（前缀和+二分）的相关教程结束。