P1314 NOIP2011T5 聪明的质检员 二分+前缀和

题意：是说在给定的区间内，将所有满足 w_i>W的矿石个数和这些矿石的价值之和乘起来所得的数就是这个区间的检验值 Y_i，然后将所有的 Y加起来，与标准值 S作差，取绝对值与 ans比较，最后得出答案

解法：二分+前缀和；

1.二分：看看题目数据，如果枚举每一个值，并去检验，那么肯定会 T掉；

2.前缀和：由于需要多次检验，顾可以使用前缀和进行优化；

附上代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define ll long long
using namespace std;
const int N = 200086;
const int inf = 2147483647;

inline int read(){
	int ref=0,x=1; char ch=getchar();
	while(!isdigit(ch)){if(ch==‘-‘)x=-1;ch=getchar();}
	while(isdigit(ch)){ref=ref*10+ch-‘0‘;ch=getchar();}
	return ref*x;
}

ll n,m,S;
ll w[N],v[N],l[N],r[N];
ll a[N],b[N];
ll maxn=-1,minn=inf,ans=9223372036854775801;
ll s,sum;

bool check(int x){
	s=0,sum=0;
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	for(int i=1;i<=n;i++){
		if(w[i]>x) a[i]=a[i-1]+1,b[i]=b[i-1]+v[i];
		else a[i]=a[i-1],b[i]=b[i-1];
	}
	for(int i=1;i<=m;i++) s+=(a[r[i]]-a[l[i]-1])*(b[r[i]]-b[l[i]-1]);
	sum=llabs(s-S);
	if(s>S) return true;
	else return false;
}

int main()
{
	scanf("%lld%lld%lld",&n,&m,&S);
	for(int i=1;i<=n;i++){
		w[i]=read(),v[i]=read();
		maxn=max(maxn,w[i]);
		minn=min(minn,w[i]);
	}
	for(int i=1;i<=m;i++) l[i]=read(),r[i]=read();
	int left=minn-1,right=maxn+1;
	while(left<=right){
		ll mid=(left+right)>>1;
		if(check(mid)) left=mid+1;
		else right=mid-1;
		if(sum<ans) ans=sum;
	}
	printf("%lld",ans);
	return 0;
}