題目描述：
題目背景： NOIP2011 DAY2 試題 2 。
小T是一名品質監督員，最近負責檢驗一批礦産的品質。這批礦産共有 n 個礦石，從 1 到 n 逐一編号，每個礦石都有自己的重量 wi 以及價值 vi。檢驗礦産的流程是：
1、給定 m 個區間[Li,Ri]；
2、選出一個參數 W ；
3、對于一個區間[Li,Ri]，計算礦石在這個區間上的檢驗值 Yi：
這批礦産的檢驗結果Y 為各個區間的檢驗值之和。即：
若這批礦産的檢驗結果與所給标準值 S 相差太多，就需要再去檢驗另一批礦産。小 T 不想費時間去檢驗另一批礦産，是以他想通過調整參數 W 的值，讓檢驗結果盡可能的靠近标準值 S ，即使得 S-Y 的絕對值最小。請你幫忙求出這個最小值。
輸入格式：
第一行包含三個整數 n，m，S，分别表示礦石的個數、區間的個數和标準值。
接下來的 n 行，每行 2 個整數，中間用空格隔開，第 i+1 行表示 i 号礦石的重量 wi 和價值 vi 。
接下來的 m 行，表示區間，每行 2 個整數，中間用空格隔開，第 i+n+1 行表示區間 [Li,Ri] 的兩個端點 Li 和 Ri。注意：不同區間可能重合或互相重疊。
輸出格式：
輸出隻有一行，包含一個整數，表示所求的最小值。
樣例輸入：
5 3 15
1 5
2 5
3 5
4 5
5 5
1 5
2 4
3 3
樣例輸出：
10
備注：
樣例說明：當 W 選 4 的時候，三個區間上檢驗值分别為 20、5、0，這批礦産的檢驗結果為 25，此時與标準值 S 相差最小為 10 。
資料範圍：
對于 10% 的資料，有 1≤n，m≤10；
對于 30% 的資料，有 1≤n，m≤500；
對于 50% 的資料，有 1≤n，m≤5,000；
對于 70% 的資料，有 1≤n，m≤10,000；
對于 100% 的資料，有 1≤n，m≤200,000；0<wi,vi≤106；0<S≤1012；1≤Li≤Ri≤n。
題目分析：
二分法。表示看不懂第一個求和，後來問了别人才知道是滿足要求的個數。就直接二分w，顯然w越大，計算出來的y越小。如果計算出來的y大于了s，就把w變大，反之，把w變小。
附代碼：
#include<iostream>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<ctime>
#include<set>
#include<queue>
#include<map>
#include<map>
#include<iomanip>
#include<algorithm>
using namespace std;
const int maxn=+;
int n,m,num[maxn],w[maxn],v[maxn],l[maxn],r[maxn];
long long sum[maxn],ans,s;
int readint()
{
char ch;int i=,f=;
for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
if(ch=='-') {ch=getchar();f=-;}
for(;ch>='0'&&ch<='9';ch=getchar()) i=(i<<)+(i<<)+ch-'0';
return i*f;
}
long long check(int x)
{
memset(num,,sizeof(num));
memset(sum,,sizeof(sum));
ans=;
for(int i=;i<=n;i++)
{
num[i]=num[i-];
if(w[i]>=x) num[i]++;
sum[i]=sum[i-];
if(w[i]>=x) sum[i]+=v[i];
}
for(int i=;i<=m;i++)
ans+=((num[r[i]]-num[l[i]-])*(sum[r[i]]-sum[l[i]-]));
return ans;
}
long long half()
{
int l=,r=,mid;
long long ret,ret1,ret2,ret3;
while(l<=r)
{
mid=(l+r)>>;
ret=check(mid);
if(ret==s) break;
if(ret>s)
l=mid+;
else
r=mid-;
}
if(ret==s) return ret;
ret1=check(l);ret2=check(r);
if(abs(ret1-s)<=abs(ret2-s)) return ret1;//因為最後l，r會是一大一小，但誰離s近并不确定，需要判斷。
if(abs(ret2-s)<=abs(ret1-s)) return ret2;
}
int main()
{
//freopen("lx.in","r",stdin);
n=readint();m=readint();scanf("%I64d",&s);
for(int i=;i<=n;i++)
{
w[i]=readint();
v[i]=readint();
}
for(int i=;i<=m;i++)
{
l[i]=readint();
r[i]=readint();
}
printf("%I64d",abs(half()-s));
return ;
}