题解 P1314 【聪明的质监员】
teafrogsf
2017-09-12 21:41:02
## 博客即是洛谷blog。
本题是一个比较明显的二分题，显然可以看出来这个标准值S是可以二分的，之后如果暴力O(nmlog1e6)就是50分。
但我们显然不用暴力，这里我们可以先预扫一遍数组，并用前缀和存w和v，之后再一个O(m)暴力判断就可以了。
和大于标准时加大l以加大mid，小于时减少r。
**并一定要注意l和r的初始大小**，l为所有值中最小-1~~虽然貌似不减也可以过~~，r为最大值+1。
```cpp
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#define neko 300010
#define f(i,a,b) for(register int i=a;i<=b;++i)
typedef long long ll;
struct node
{
int l,r;
}q[neko];
int n,m,l,r,mid,minn=1000000000,maxn,w[neko],c[neko];
ll stdd,sum,ans=1e13,v[neko],s[neko];
int main()
{
int i,j;
scanf("%d%d%lld",&n,&m,&stdd);
f(i,1,n)scanf("%d%lld",&w[i],&v[i]),minn=std::min(minn,w[i]),maxn=std::max(maxn,w[i]);
l=minn-1,r=maxn+1;
f(i,1,m)scanf("%d%d",&q[i].l,&q[i].r);
while(l<r)
{
mid=(l+r)>>1,sum=0,memset(c,0,sizeof(c)),memset(s,0,sizeof(s));
f(i,1,n)
{
if(w[i]>=mid)c[i]=c[i-1]+1,s[i]=s[i-1]+v[i];
else c[i]=c[i-1],s[i]=s[i-1];
}
f(i,1,m)sum+=(c[q[i].r]-c[q[i].l-1])*(s[q[i].r]-s[q[i].l-1]);
//printf("%d %d %d %d\n",l,r,mid,sum);
if(llabs(stdd-sum)<ans)ans=llabs(stdd-sum);
if(sum>stdd)l=mid+1;
else r=mid;
}printf("%lld\n",ans);
return 0;
}
O(m(n)log1e6)。
```