P1314 聪明的质监员 解题报告
无秒
2020-05-19 18:26:59
仔细看题目，它是由w求值，然后需要找出|y-s|的最小值，根据以往的经验，都是二分，然后用一个特殊的chech()函数来不断缩小范围求出答案。
首先，考虑二分范围，就是v中最小值到最大值。其次，如何判断？二分分的是w，可以看出w越大，能取上的值越少，所以check()函数要求出y，当y>s时，w还要更大来使y更小。
so，关键就是y怎么求？随便列举一个区间，当这个w[i]>w时，我们就要把左边的那个求和++，右边那个求和的加上v[i]嘛。但是它的区间有m个啊，每次都一个个算太耗时间了丫！不难发现，其实有些算的是重复的，只要搞出前缀和来优化一下，那么计算就变成O(1)的了。
上代码：
```cpp
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int maxx=-1,minn=2147483647,n,m;
long long ans=0x3f3f3f3f3f3f3f3f,s,y,sum;
int w[200001],v[200001],l[200001],r[200001];
long long sn[200001],sv[200001];
inline void read(int &x)
{
x=0;int f=0;char ch=getchar();
while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=f?-x:x;
}
bool check(int W)
{
y=0;sum=0;
memset(sn,0,sizeof(sn));
memset(sv,0,sizeof(sv));
for(int i=1;i<=n;i++)
{
if(w[i]>=W) sn[i]=sn[i-1]+1,sv[i]=sv[i-1]+v[i];
else sn[i]=sn[i-1],sv[i]=sv[i-1];
}
for(int i=1;i<=m;i++)
y=y+(sn[r[i]]-sn[l[i]-1])*(sv[r[i]]-sv[l[i]-1]);
sum=llabs(y-s);
if(y>s) return true;
return false;
}
int main()
{
scanf("%d%d%lld",&n,&m,&s);
for(int i=1;i<=n;i++)
{
read(w[i]);read(v[i]);
maxx=max(maxx,v[i]);
minn=min(minn,v[i]);
}
for(int i=1;i<=m;i++)
{
read(l[i]);read(r[i]);
}
int right=2+maxx,left=minn-1,mid;
while(left<=right)
{
mid=(left+right)>>1;
if(check(mid)) left=mid+1;
else right=mid-1;
if(sum<ans) ans=sum;
}
printf("%lld\n",ans);
return 0;
}
```