题解 P1314 【聪明的质监员】
hicc0305
2018-06-19 18:26:49
### 【问题描述】
小 T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有 n 个矿石，从 1 到 n 逐一编号，每个矿石都有自己的重量 wi 以及价值 vi。检验矿产的流程是：
1、给定 m 个区间[Li，Ri]；
2、选出一个参数 W；
3、对于一个区间[Li，Ri]，计算矿石在这个区间上的检验值 Yi ：
这批矿产的检验结果 Y 为各个区间的检验值之和。即： Y1+Y2...+Ym
若这批矿产的检验结果与所给标准值 S 相差太多，就需要再去检验另一批矿产。小T不想费时间去检验另一批矿产，所以他想通过调整参数W 的值，让检验结果尽可能的靠近标准值 S ，即使得 S−Y 的绝对值最小。请你帮忙求出这个最小值。
### 【输入数据】
第一行包含三个整数 n,m,Sn,m,S ，分别表示矿石的个数、区间的个数和标准值。
接下来的 nn 行，每行 22 个整数，中间用空格隔开，第 i+1i+1 行表示 ii 号矿石的重量 w_iw
i
和价值 v_iv
i
。
接下来的 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
### 【输出样例 1】
10
### 【数据范围】
对于 10% 的数据，有 1 ≤n ,m≤101≤n,m≤10 ；
对于 30% 的数据，有 1 ≤n ,m≤5001≤n,m≤500 ；
对于 50% 的数据，有 1 ≤n ,m≤5,0001≤n,m≤5,000 ；
对于 70% 的数据，有 1 ≤n ,m≤10,0001≤n,m≤10,000 ；
对于 100% 的数据，有 1≤ n ,m ≤200,000,0< wi,vi ≤10^6,0< S ≤10^12,1 ≤Li ≤ Ri ≤ n,1 ≤n,m ≤200,000,0< wi,vi ≤10^6,0< S ≤10^12,1≤ Li ≤ Ri ≤n。
------------
只需要二分答案，找离s最近的答案即可，并不难
```cpp
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define N 200001
#define M 200001
#define ll long long
using namespace std;
int n,m,l[M],r[M],v[N],w[N];
int maxw;
ll ans,tmp,s;
ll sumv[N],sumi[N];
ll judge(int W){
ll res = 0;
sumv[0] = sumi[0] = 0ll;
for(int i = 1;i <= n;i++){
if(w[i] >= W)sumv[i] = sumv[i - 1] + (ll)v[i],sumi[i] = sumi[i - 1] + 1ll;
else sumv[i] = sumv[i - 1],sumi[i] = sumi[i - 1];
}
for(int i = 1;i <= m;i++)
res += (sumi[r[i]] - sumi[l[i] - 1]) * (sumv[r[i]] - sumv[l[i] - 1]);
return res;
}
int main()
{
scanf("%d %d %lld",&n,&m,&s);
for(int i = 1;i <= n;i++)
scanf("%d %d",&w[i],&v[i]),maxw = max(maxw,w[i]);
for(int i = 1;i <= m;i++)
scanf("%d %d",&l[i],&r[i]);
int L = 1,R = maxw;
while(L <= R){
int mid = (L + R) / 2;
tmp = judge(mid);
if(tmp <= s)R = mid - 1;
else L = mid + 1;
if(abs(s - ans) > abs(tmp - s))ans = tmp;
}
printf("%lld",abs(ans - s));
return 0;
}
```