35分超级蒟蒻,求各位大神巨佬查错。。

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

微雨燕双飞 @ 2018-07-07 19:41:41

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
const int M=2e5+10;
int n,m,w[N],v[N],l[M],r[M],low,high,mid;
long long s,cnt,ans=999999999999999,prenum[N],prevalue[N],tot;
void init(int W)
{
  memset(prenum,0,sizeof(prenum));
  memset(prevalue,0,sizeof(prevalue));
  for(int i=1; i<=n; i++)
  {
    prenum[i]=prenum[i-1];
    prevalue[i]=prevalue[i-1];
    if(w[i]>=W)
    {
      prenum[i]++;
      prevalue[i]+=v[i];
    }
  } 
}
bool check(int W)
{
  init(W);
  cnt=0;
  for(int i=1; i<=m; i++)
    cnt+=(prenum[r[i]]-prenum[l[i]-1])*(prevalue[r[i]]-prevalue[l[i]-1]);
  tot=llabs(cnt-s);
  return cnt>s;
}
int main()
{
  scanf("%d%d%d",&n,&m,&s);
  low=2e9; high=0;
  for(int i=1; i<=n; i++) 
  {
    scanf("%d%d",&w[i],&v[i]);
    low=min(low,w[i]);
    high=max(high,w[i]);
  }
  for(int i=1; i<=m; i++) scanf("%d%d",&l[i],&r[i]);
  low--; high+=2;
  while(low<=high)
  {
    mid=(low+high)>>1;
    if(check(mid)) low=mid+1;
      else high=mid-1;
    ans=min(ans,tot); 
  }
  printf("%lld\n",ans);
  return 0;
}

by 微雨燕双飞 @ 2018-07-07 19:42:23

init子过程是预处理前缀和,check子函数是二分答案的判断函数


by 微雨燕双飞 @ 2018-07-07 19:43:26

实在是没有发现有什么地方不对,35分也太神奇了吧?还望各位大神不吝赐教。


by 明依 @ 2020-06-21 15:42:08

一看就是和我一样不仔细的人

s要用long long读入


|