[NOIP2011] 聪明的质监员
题目描述
小T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有 \(n\) 个矿石，从 \(1\) 到 \(n\) 逐一编号，每个矿石都有自己的重量 \(w_i\) 以及价值 \(v_i\) 。检验矿产的流程是：
- 给定 \(m\) 个区间 \([l_i, r_i]\) ;
- 选出一个参数 \(W\) ;
- 对于一个区间 \([l_i, r_i]\) ，计算矿石在这个区间上的检验值 \(y_i\)：
\(y_i = \displaystyle \sum^{r_i}_{j = l_i}{[w_j\geq W]} \times \displaystyle \sum^{r_i}_{j = l_i}{[w_j\geq W]}v_i\)
其中 \(j\) 为矿石编号。
这批矿产的检验结果 \(y\) 为各个区间的检验值之和。即： \(\displaystyle \sum^{m}_{i = 1}{y_i}\)
若这批矿产的检验结果与所给标准值 \(s\) 相差太多，就需要再去检验另一批矿产。小T 不想费时间去检验另一批矿产，所以他想通过调整参数 \(W\) 的值，让检验结果尽可能的靠近标准值 \(s\) ，即使得 \(∣s−y∣\) 最小。请你帮忙求出这个最小值。
输入格式
第一行包含三个整数 \(n,m,s\) ，分别表示矿石的个数、区间的个数和标准值。
接下来的 \(n\) 行，每行两个整数，中间用空格隔开，第 \(i+1\) 行表示 \(i\) 号矿石的重量 \(w_i\) 和价值 \(v_i\) 。
接下来的 \(m\) 行，表示区间，每行两个整数，中间用空格隔开，第 \(i+n+1\) 行表示区间 \([l_i, r_i]\) 的两个端点 \(l_i\) 和 \(r_i\) 。注意：不同区间可能重合或相互重叠。
输出格式
一个整数，表示所求的最小值。
数据范围
对于 \(100\%\) 的数据，有 \(1 \leq n, m \leq 200,000, 0 < w_i, v_i \leq 10^6, 0 < s \leq 10^{12}, 1 \leq l_i \leq r_i \leq n\) 。
题解
显然，选取的 \(W\) 越大，被选中的数就更少， \(y\) 就越小。不难看出， \(|y - s|\) 关于 \(W\) 是先降再升的单峰函数，分界点是 \(y = s\)。因此我们可以通过二分 \(W\) 的值来寻找最优解。
下面考虑验证。对于一个已经确定的 \(W\) ，每一段区间的测量值都是确定的，不存在策略的差异。因此只需要对每一个区间求测量值再求和即可。因为测量值为区间内符合条件的矿产的数目和 \(\times\) 符合条件的矿产的价值和，需要分别对两个目标求和，采用两个前缀和维护即可。
注意二分的条件。
AC代码
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <stack>
#include <queue>
#define int long long
using namespace std;
const int MAXN = 2e5 + 3;
int n, m, s;
int w[MAXN], v[MAXN], l[MAXN], r[MAXN];
inline int check(int x) {
int ans = 0;
int num[MAXN], sum[MAXN];
for (int i = 0; i <= n; i++) sum[i] = num[i] = 0;
for (int i = 1; i <= n; i++) {
num[i] = num[i - 1], sum[i] = sum[i - 1];
if (w[i] >= x) {
num[i]++, sum[i] += v[i];
}
}
for (int i = 1; i <= m; i++) {
ans += (num[r[i]] - num[l[i] - 1]) * (sum[r[i]] - sum[l[i] - 1]);
}
return ans;
}
int w1[MAXN];
signed main() {
cin >> n >> m >> s;
for (int i = 1; i <= n; i++) {
cin >> w[i] >> v[i];
w1[i] = w[i];
}
for (int i = 1; i <= m; i++) {
cin >> l[i] >> r[i];
}
sort(w1 + 1, w1 + 1 + n);
int nl = 1, nr = n, mid;
while (nl <= nr) {
mid = (nl + nr) >> 1;
if (check(w1[mid]) > s) nl = mid + 1;
else nr = mid - 1;
}
int ans = min(abs(check(w1[mid]) - s), min(abs(check(w1[nl]) - s), abs(s - check(w1[nr]))));
cout << ans << '\n';
return 0;
}