[NOIP2011]聪明的质监员 题解
题目大意：
额……貌似蛮清晰的，就不赘述了。
思路：
首先不难发现M越大Y越小，因此可以二分答案（方向不要弄错），二分出最小的不小于S的Y即可。而计算Y时可用前缀和O(n+m)求得。两种边界情况也要考虑一下（同时long long不要少开）。
代码：
1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 #define ll long long 5 const int M=200008; 6 int n,m,i,h,t,k,mn,mx,mid,w[M],v[M],l[M],r[M]; 7 ll s,sum[M],num[M]; 8 9 ll abs(ll x) { return x>0?x:-x; } 10 11 ll cal(int p) 12 { 13 int i; ll t=0; 14 for (i=1;i<=n;i++) 15 if (w[i]>=p) num[i]=num[i-1]+1,sum[i]=sum[i-1]+v[i]; 16 else num[i]=num[i-1],sum[i]=sum[i-1]; 17 for (i=1;i<=m;i++) t+=(num[r[i]]-num[l[i]-1])*(sum[r[i]]-sum[l[i]-1]); 18 return t; 19 } 20 21 int main() 22 { 23 scanf("%d%d%lld",&n,&m,&s),mn=1000003; 24 for (i=1;i<=n;i++) scanf("%d%d",&w[i],&v[i]),mx=max(mx,w[i]),mn=min(mn,w[i]); 25 for (i=1;i<=m;i++) scanf("%d%d",&l[i],&r[i]); 26 for (h=mn,t=++mx;h<t;) 27 { 28 mid=h+t>>1; 29 if (cal(mid)>s) h=mid+1; 30 else t=mid,k=mid; 31 } 32 if (cal(h)-s<cal(k)-s) k=h; 33 printf("%lld ",abs(min(s-cal(k),cal(k-1)-s))); 34 return 0; 35 }