题目描述

小T是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有n个矿石，从1到 n 逐一编号，每个矿石都有自己的重量wi以及价值vi。检验矿产的流程是：
1、给定m个区间[Li，Ri]；
2、选出一个参数W；

3、对于一个区间[Li，Ri]，计算矿石在这个区间上的检验值 Yi ：
Yi=∑j1∗∑jvjY_{i}=\sum_{j}{1}*\sum_{j}{v_{j}}Yi=∑j1∗∑jvj且wj≥W，j是矿石编号
这批矿产的检验结果Y为各个区间的检验值之和。即：Y=∑i=1mYiY=\sum_{i=1}^{m}{Y_{i}}Y=∑i=1mYi
若这批矿产的检验结果与所给标准值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。注意：不同区间可能重合或相互重叠。

输出描述:

输出只有一行，包含一个整数，表示所求的最小值。

示例1

输入
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。

解答

说实话，这题其实应该放到普及+/提高。思路其实就是简单的快速查找（其实你用二分或三分均可）+前缀和。
首先我们分析一下题面的式子，其实
就等于该区间内大于等于 的数字数量与大于等于 的数字之和的乘积。也就是说，我们需要将重量排序后快速查找出一个与 的答案差距最小的地方。
那么，差距最小？肯定第一个想到的就是三分。所以我们的做法就出来了（下面附上思路）：
sort();
三分枚举()
{
    if(左中点的答案<右中点的答案)	左端点=左中点;
    else	右端点=右中点;
}
那么我们就到了第二个问题：计算对于每一个 的答案。如果每一个区间都去枚举复杂度是 ，肯定会 。所以我们就需要在 的时间内处理出每一个的答案。
既然需要求的是每一个区间的答案，那么第二个算法就出来了：前缀和。我们只需要枚举每一位上的东西，然后用前缀和扫一遍统计即可。这样单次计算复杂度就降到了。
最后如果三分没有枚举完，手动枚举剩下的那一点即可。
下面附上代码：
#include<iostream>
#include<algorithm>
#define N 1000005
#define abs(a) ((a)<0?-(a):(a))
#define INF 9999999999999999ll
using namespace std;
long long ans=INF,n,m,S,w[N],v[N],l[N],r[N],sum[N],sum2[N],q[N];
long long check(int W)
{
	long long now=0;
	for(int i=1;i<=n;i++)
	{
		sum[i]=sum[i-1],sum2[i]=sum2[i-1];
		if(w[i]>=W)	sum[i]+=v[i],sum2[i]++;
	}
	for(int i=1;i<=m;i++)
		now+=(long long)(sum2[r[i]]-sum2[l[i]-1])*(sum[r[i]]-sum[l[i]-1]);
	return abs(now-S);
}
int main()
{
	cin>>n>>m>>S;q[0]=-1;
	for(int i=1;i<=n;i++)
		cin>>w[i]>>v[i],q[i]=w[i];
	for(int i=1;i<=m;i++)
		cin>>l[i]>>r[i];
	sort(q+1,q+n+1);
	int l=1,r=n;
	while(r>=l+4)
	{
		int mid=(l+r)/2,mid2=(r+mid)/2;
		if(check(q[mid])>check(q[mid2]))	l=mid;
		else	r=mid2;
	}
	for(int i=l;i<=r;i++)
		if(check(q[i])<ans)
			ans=check(q[i]);
	cout<<ans;
	return 0;
}



来源：SSH_oj