【NOIP2011提高組】聰明的質檢員

題目大意:給定一些礦石的重量和價值和一些選擇的區間，用編号在這些區間内的礦石算出一個檢驗值Y，要求檢驗值和題目所給的S的內插補點(abs(S-Y))最小。

由于算檢驗值的時候有一個參數W限制，而W未定，但是易知W應該在[minw,maxw](minw為礦石的最小重量)，是以應該窮舉所有W，對于所有的W的值，利用題目中的公式樸素地算出一個Y的值，再和之前的abs(S-Y))比較，然後取abs(S-Y)的最小值。O(maxw*m*n)而不管m還是n都是20W規模的，顯然并不能1S過。

這裡有兩個優化的方向，一個是如何快速的算出Y的值，另一個是能否不要盲目枚舉W而是用二分的想法猜W的值。

對于一：仔細觀察本題，發現本題Y的計算有一個特點，Y的計算涉及的是一個區間裡面的值，而在一個序列的某段區間上算一個值常用字首和優化。

故設字首和數組sumy[n],sumc[n],表示在[1,n]中滿足a[i].w>W(1<=i<=n)的礦石的總價值和滿足條件的礦石數量。

預處理後直接計算(sumy[b]-sumy[a-1])*(sumc[b]-sumc[a-1])即可。

對于二：由于本題所求是差的絕對值最小，這個要求有兩種含義。

1.在Y小于等于S的前提下Y最大,2.在Y大于S時Y最小。

分别針對兩種情況猜W，最後在比較一次取最小值。

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<queue>
#include<algorithm>
#include<cstring>
#define maxn 200010
using namespace std;
typedef long long LL;
LL n,m,maxw=0;
LL S;
LL sumc[maxn],sumy[maxn];
const LL inf=40000000000000000ll;

void _read(LL &x)//由于本題讀入次數多，為了節約時間用的手工輸入
{
	x=0;
	char ch=getchar();
	while(ch<'0' || ch>'9') ch=getchar();
	while(ch>='0' && ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
}
struct mine//礦石 
{
	LL w,v;
}p[maxn];

struct data//區間 
{
	LL a,b;
}q[maxn];

LL calc(LL W)
{
	LL YY=0;
	for(int i=1;i<=n;i++)
	{
		sumc[i]=sumc[i-1];
		sumy[i]=sumy[i-1];
		if(p[i].w>=W)
		{
			sumc[i]++;
			sumy[i]+=p[i].v;
		}
	}
	
	for(int i=1;i<=m;i++)
	YY+=(sumc[q[i].b]-sumc[q[i].a-1])*(sumy[q[i].b]-sumy[q[i].a-1]);
		return YY;
}

void solve()//猜W 
{
	LL A1=0,B1=10000000,A2=0,B2=10000000,t1=-inf,t2=inf;
	for(int i=0;i<50;i++)
	{
		LL W1=A1+B1>>1,tt1=calc(W1);
		if(tt1<=S)
		t1=tt1,B1=W1;
		else
		A1=W1;
		
		LL W2=A2+B2>>1,tt2=calc(W2);
		if(tt2>S)
		t2=tt2,A2=W2;
		else
		B2=W2;
	}
	
	LL ans=min(abs(S-t1),abs(S-t2));
	
	cout<<ans<<endl;
}

int main()
{
	//freopen("qc.in","r",stdin);
	//freopen("qc.out","w",stdout);
	
	//scanf("%d%d",&n,&m);
	//cin>>S;
	_read(n);
	_read(m);
	_read(S);
	
	for(int i=1;i<=n;i++)
	{
	_read(p[i].w);
	_read(p[i].v);
	maxw=max(maxw,p[i].w);
	}
	for(int i=1;i<=m;i++)
	{
		_read(q[i].a);
		_read(q[i].b);
	}

	solve();
	
	return 0;
}