P1314 聪明的质检员 题解
这个题的总体思路————二分，还是不难想的
就是如何处理前缀和比较难想（好吧是我太弱了）
虽然题面给的计算式貌似很复杂的样子
但是其实就是 检验值=区间内满足w[i]>W的矿石个数 * ∑v[i]
因此我们二分判断时，如果检验结果（检验值之和）大于标准值，就说明我们二分出的W还可以再变大，不然就说明W太大了，可以变小试一下，然后记录最小的差值
关于二分停不了导致TLE的问题，我们可以加一个cnt记录二分次数，理论上讲二分50次应该是足够了
下面贴AC代码：
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,v[200010],w[200010];
int l[200010],r[200010];
long long s,cur,sum,ans,pre_v[200010],pre_n[200010];
bool check(int mid)
{
cur=0;sum=0;//因为每次二分出的mid值都不一样
memset(pre_n,0,sizeof(pre_n));//所以留下的矿石也不尽相同
memset(pre_v,0,sizeof(pre_v));//因此要初始化数组和全局变量为0
for(int i=1;i<=n;i++)
{
if(w[i]>=mid)pre_v[i]=pre_v[i-1]+v[i],pre_n[i]=pre_n[i-1]+1;//如果符合条件才记录前缀和
else pre_v[i]=pre_v[i-1],pre_n[i]=pre_n[i-1];
}
for(int i=1;i<=m;i++)
cur+=(pre_n[r[i]]-pre_n[l[i]-1])*(pre_v[r[i]]-pre_v[l[i]-1]);//计算检查值
sum=llabs(cur-s);//llabs()是algorithm库里的函数
return cur>s;//判断cur与s的大小
}
int main()
{
int maxx=-1,minn=0x7fffffff;
scanf("%d%d%lld",&n,&m,&s);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&w[i],&v[i]);
maxx=max(maxx,w[i]);//确定二分上下限
minn=min(minn,w[i]);
}
for(int i=1;i<=m;i++)
scanf("%d%d",&l[i],&r[i]);
int r=maxx,l=minn,mid,cnt=0;
ans=999999999999999;//不要忘了这一步
while(l<=r)
{
cnt++;
if(cnt>50)break;//防止无限循环
mid=(l+r)>>1;
if(check(mid))l=mid+1;
else r=mid-1;
if(sum<ans)ans=sum;
}
printf("%lld",ans);//注意lld
return 0;
}