题解 P1314 【聪明的质监员】

吐槽一下，这个质检员不会被开除么。。。。 这个题很明显的二分枚举，但是还有一个前缀和有点坑人。 这题题其实点不多，就两个关键点： ## 第一：二分的判断。 可以看到：在W取0时，所有的区间内的矿石都可以选上， 而在W大于最大的质量时，所有的矿石都选不上。 然后简单算一下就发现： W越大，矿石选的越少，W越小，矿石选的越多。 ### 所以，随着W增大，Y值减小； 所以：二分的判断条件出来了： 当$Y>s$ 时，需要增大$W$来减小$Y$,从而$|Y-s|$变小； 当$Y==s$时，$|Y-s|==0$; 当$Y<s$时，需要减小W来增大$Y$，从而$|Y-s|$变大； ## 第二：前缀和。 我们在计算一个区间的和时（虽然这里是两个区间和再相乘，但没关系） 通常是用前缀和的方法来缩减时间，直接模拟是$n^2$的，而前缀和成了$2*n$ 大大的优化了时间，前缀和不会的去先学前缀和，我默认大家都会，就不赘述了。 很显然： 在$w[i]>=W$时这个i矿石会在统计里（若$<W$就不管它了直接$pre[i]=pre[i-1]$）， 矿石价值和是：$pre_v[i]=pre_v[i-1]+v[i]$，前面的和加上当前这一个i矿石; 矿石数量和是：$pre_n[i]=pre_n[i-1]+1$，数量加1嘛。 然后最后算的时候用右端点r-（左端点l-1）就可以了 ### 注意：谨记所前缀和时要pre[r]-pre[l-1]，这个‘-1’不要忘！ 然后就没啥了，给上代码： （当然，一些基础的“lld”之类的你要注意,不多赘述了） ```cpp #include<bits/stdc++.h> using namespace std; const int maxn=200010; int w[maxn],v[maxn],l[maxn],r[maxn]; long long pre_n[maxn],pre_v[maxn]; long long Y,s,sum; int n,m,mx=-1,mn=2147483647; bool check(int W) { Y=0,sum=0; memset(pre_n,0,sizeof(pre_n)); memset(pre_v,0,sizeof(pre_v)); for(int i=1;i<=n;i++) { if(w[i]>=W) pre_n[i]=pre_n[i-1]+1,pre_v[i]=pre_v[i-1]+v[i]; else pre_n[i]=pre_n[i-1],pre_v[i]=pre_v[i-1]; } for(int i=1;i<=m;i++) Y+=(pre_n[r[i]]-pre_n[l[i]-1])*(pre_v[r[i]]-pre_v[l[i]-1]); sum=llabs(Y-s); if(Y>s) return true; else return false; } int main(){ // freopen("qc.in","r",stdin); // freopen("qc.out","w",stdout); scanf("%d %d %lld",&n,&m,&s); for(int i=1;i<=n;i++) { scanf(" %d %d",&w[i],&v[i]); mx=max(mx,w[i]); mn=min(mn,w[i]); } for(int i=1;i<=m;i++) scanf(" %d %d",&l[i],&r[i]); int left=mn-1,right=mx+2,mid; //这里有的人说要特判左右端点的check，但是其实你把left开成mn-1,right开成mx+2(注意取mx+1时即为W比所有都大，Y是0，这个情况要考虑，所以+2包含mx+1)就可以包含左右端点的check了，会简单点。 long long ans=0x3f3f3f3f3f3f3f3f;//ll 范围内的无穷大，近似于(maxll/2)的大小 while(left<=right) { mid=(left+right)>>1; if(check(mid)) left=mid+1; else right=mid-1; if(sum<ans) ans=sum; } printf("%lld",ans); return 0; } ```