记录编号	34128	评测结果	RRRRRRRRRR
题目名称	[NOIP 2011]选择客栈	最终得分	0
用户昵称	权限狗	是否通过	未通过
代码语言	C++	运行时间	0.002 s
提交时间	2011-11-30 20:35:06	内存使用	8.81 MiB

#include<fstream>
using namespace std;
ifstream fin("qc.in");
ofstream fout("qc.out");
const int Infinite=100000000;
long long Min=Infinite,n,m,S;
int L[200001],R[200001],T[200001],A[200001],B[200001];
		bool bo[200001];

class 
{
public:
	int w,v;
}C[200001];
int Abs(int obj)
{
	return (obj>0?obj:0-obj);
}
void Init()
{
int i,j;
	for(i=1;i<=n;i++)
		fin>>C[i].w>>C[i].v;
	for(i=1;i<=m;i++)
	{
		fin>>L[i]>>R[i];
		for(j=L[i];j<=R[i];j++)
			T[j]++;
	}
}
int main()
{
int i,j;
	fin>>n>>m>>S;
	Init();
	int Max=0;
	for(i=1;i<=n;i++)
		if(Max<C[i].w)
			Max=C[i].w;
	int l=1,r=Max;
	for(; l<r ;)
	{
		int I=0,W=l+r;
		int Num=0,record=0;
		W>>=1;
		for(i=1;i<=n;i++)
		{
			A[i]=A[i-1];
			B[i]=B[i-1];
			if(C[i].w >= W)
			{				
				A[i]++;
				B[i]+=C[i].v;
			}
		}
		for(i=1;i<=m;i++)
			I+=(A[R[i]]-A[L[i-1]]) * (B[R[i]]-B[L[i-1]]);
		if(I<S)
		{
			if(Abs(I-S) < Min)
				Min=I;
			r=W;
		}
		else
		{
			if(Abs(I-S) < Min)
				Min=I;
			l=W+1;
		}
		
	}
	
	fout<<Abs(Min-S);
	
	fin.close();
	fout.close();
	return 0;
}
/*
优化:用A,B两个数组分别记录在到i时
*/