orz 各路大神看看什么地方错了,只有55分

P1314 [NOIP2011 提高组] 聪明的质监员

山雨木子 @ 2017-12-24 10:23:07

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
typedef long long ll;
using namespace std;
int sum1[200010],sum2[200010];
ll ans=0x7fffffff,s,n,m;
ll L,R;
int w[200010],v[200010],l[200010],r[200010];
ll labs(ll a )
{
    return a<0?-a:a;
}
int judge(ll mid)
{
    memset(sum1,0,sizeof(sum1));
    memset(sum2,0,sizeof(sum2));
    for(int i=1;i<=n;i++)
      {
          sum1[i]=sum1[i-1];//表示1->i中大于标准的数量。
        sum2[i]=sum2[i-1];//表示1->i中大于标准的矿石的价值之和
        if(w[i]>=mid)
          {
              sum1[i]++;
              sum2[i]+=v[i];
           } 
      }
      long long y=0;
    for(int i=1;i<=m;i++)
    {
        y+=(sum1[r[i]]-sum1[l[i]-1])*(sum2[r[i]]-sum2[l[i]-1]);
    }
     ans=min(ans,labs(y-s));
     return y-s>0;
}
int main()
{
 scanf("%lld%lld%lld",&n,&m,&s);
 for(int i=1;i<=n;i++)
      {
      scanf("%d%d",&w[i],&v[i]);
      R= max(R,(ll)w[i]);  
      }
 for(int i=1;i<=m;i++)
  scanf("%d%d",&l[i],&r[i]); 
  R++;
  while(L<=R)
   {
   ll mid=(L+R)/2;
        if(judge(mid))
            L=mid+1;
        else
            R=mid-1;
   }
   printf("%lld",ans);
   return 0;
}

|