【洛谷P1314】[NOIP2011]聪明的质监员

聪明的质监员

题目链接：https://www.luogu.org/problemnew/show/P1314

Y（W）随W的值增大而减小

二分W的值，找到最小的W使得Y（W）>S；

比较Y（W）和Y（W-1）与S的差值。

计算Y（W）：

O（n）预处理一维前缀和数组，

O（m）暴力计算出Y（W）

 #include<cstdio>

 using namespace std;

 long long n,m,S,ranges[][],w[],v[];

 inline long long abs(long long x)

 {

     if(x<) x=-x;

     return x;

 }

 inline long long min(long long a,long long b)

 {

     return a<b?a:b;

 }

 long long sum1[],sum2[];

 long long Y(long long x) //计算Y(W)

 {

     long long ans=;

     sum1[]=;sum2[]=;

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

      if(w[i]>x) {

          sum1[i]=sum1[i-]+;　　　　//前缀和数组sum1记录个数和

          sum2[i]=sum2[i-]+v[i];　　//sum2记录价值和

      }

      else {

          sum1[i]=sum1[i-];

          sum2[i]=sum2[i-];

      }

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

     {

         int l=ranges[i][],r=ranges[i][];

         ans+=(sum1[r]-sum1[l-])*(sum2[r]-sum2[l-]);

     }

     return ans;

 }

 int main()

 {

     int l=,r=;

     scanf("%lld%lld%lld",&n,&m,&S);

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

     {

         scanf("%lld%lld",&w[i],&v[i]);

         if(w[i]>r) r=w[i];

     }

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

      scanf("%lld%lld",&ranges[i][],&ranges[i][]);

     while(l<r)　　　　　　　　　　　//二分W

     {

         int mid=(l+r)>>;

         if(Y(mid)>=S) l=mid+;

         else r=mid-;

     }

     if(Y(l)<S) l-=;

     printf("%lld\n",min(abs(Y(l)-S),abs(Y(l+)-S)));

     return ;

 }