记录编号	201886	评测结果	AAAAAAAAWAAAAWAAAAAA
题目名称	631.[NOIP 2011]聪明的质监员	最终得分	90
用户昵称	yushi	是否通过	未通过
代码语言	C++	运行时间	0.407 s
提交时间	2015-10-31 15:17:38	内存使用	4.89 MiB

#include<iostream>
#include<fstream>
using namespace std;
ifstream fin("qc.in");
ofstream fout("qc.out");
int n,m;
long long S;
struct Request{
	int l;
	int r;
}request[200001];
int W[200001],v[200001],sum[200001],ans[200001];
void getsum(int w)				//sum[i]表示1到i间重量>=W的数量
{
	sum[1]=(W[1]>w)?1:0;
	for(int i=2;i<=n;i++)
	{
		if(W[i]>=w)
			sum[i]=sum[i-1]+1;
		else
			sum[i]=sum[i-1];
	}
}
void getans(int w)				//ans[i]为1到i间重量>=W的质量和
{
	ans[1]=(W[1]>w)?v[1]:0;
	for(int i=2;i<=n;i++)
	{
		if(W[i]>=w)
			ans[i]=ans[i-1]+v[i];
		else
			ans[i]=ans[i-1];
	}
}
long long gety(int w)					//对于一个w计算一次检验结果Y
{
	getsum(w);
	getans(w);
	long long s=0;
	for(int i=1;i<=m;i++)
	{
		int x=request[i].l;
		int y=request[i].r;
		s+=(sum[y]-sum[x-1])*(ans[y]-ans[x-1]);
	}
	return s;
}
long long abs(long long a)
{
	return (a<0)?(-a):a;
}
int main()
{
	fin>>n>>m>>S;
	int i,maxw=-1;
	for(i=1;i<=n;i++)
	{
		fin>>W[i]>>v[i];
		if(maxw<W[i])
			maxw=W[i];
	}
	for(i=1;i<=m;i++)
		fin>>request[i].l>>request[i].r;
	int w=maxw;				//最大重量
	int l=1,r=w;
	w >>= 1; 
	long long j,k;
	for(;;)
	{
		long long t=gety(w);
		if(t>S)//y比s大，则说明w不够大，二分上半部分 
		{
			l=w;
			if(r==w || r==w+1)
			{
				if(w+1<=maxw)
				{
					j=gety(w+1);
					j=abs(S-j);
					k=abs(S-t);
					fout<<((j<k)?j:k);
				}
				else
					fout<<abs(S-t);
				break;
			}
			w=(r+w)>>1;
		}
		else if(t<S)//y比s小，则说明w不够小，二分下半部分 
		{
			r=w;
			if(l==w || w==l+1)
			{
				if(w-1>=1)
				{
					j=gety(w-1);
					j=abs(S-j);
					k=abs(S-t);
					fout<<((j<k)?j:k);
				}
				else
					fout<<abs(S-t);
				break;
			}
			w=(l+w)>>1;
		}
		else //相等
		{
			cout<<"0";
			break;
		} 	
	}
	return 0;
}