题解 P1314 【聪明的质监员】

· · 题解

一道比较简单的二分答案的题 观察得知w参数的变化使得Y具有单调性 所以由此可以想到二分w

而数据n m都是小于200000 所以直接开sum[i][j]表示i到j比w大的个数和价值和肯定不行 由此我们又想到了前缀和思想

sum1表示从1到i比w大的个数,sum2表示从1到i比w大的价值总和

由此

for(int i=1;i<=n;i++)
  {
      if(st[i].w>=w) sum1[i]=sum1[i-1]+1,sum2[i]=sum2[i-1]+st[i].v;
      else sum1[i]=sum1[i-1],sum2[i]=sum2[i-1];
  }
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
const long long Inf=12425374554373ll;
int n,m;
long long s;
long long minn=Inf;
struct node{
    long long v,w;
}st[2000010];
long long l[200010],r[200010];
long long sum1[200010],sum2[200010];//sum1表示从1到i比w大的个数,sum2表示从1到i比w大的价值总和 
long long le=Inf,ri=-1,ans;
long long count(int w)
{    
  long long cnt=0;sum1[0]=sum2[0]=0;
  for(int i=1;i<=n;i++)
  {
      if(st[i].w>=w) sum1[i]=sum1[i-1]+1,sum2[i]=sum2[i-1]+st[i].v;
      else sum1[i]=sum1[i-1],sum2[i]=sum2[i-1];
  } //预处理从1到i之间的关系 为后面的计算做好准备
  for(int i=1;i<=m;i++)
   cnt+=(sum2[r[i]]-sum2[l[i]-1])*(sum1[r[i]]-sum1[l[i]-1]); 
  return s-cnt;
}
int main()
{
    int sum=0;
    scanf("%d%d%lld",&n,&m,&s);
    for(int i=1;i<=n;i++)
    {
      scanf("%d%d",&st[i].w,&st[i].v);
      le=min(le,st[i].w);ri=max(ri,st[i].w);    
    } 
    for(int i=1;i<=m;i++) scanf("%d%d",&l[i],&r[i]);
    while(le<=ri)
    {
        int mid=(le+ri)/2;
        ans=count(mid);
        minn=min(abs(ans),minn);
        if(ans<0) le=mid+1;         
        else if(ans>0) ri=mid-1;
        else {minn=0;break;}
    }
    printf("%lld",minn);
    return 0;
}