【题目来源】
洛谷：[P1314 NOIP 2011 提高组] 聪明的质监员 - 洛谷
【题目描述】
小T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有 \(n\) 个矿石，从 \(1\) 到 \(n\) 逐一编号，每个矿石都有自己的重量 \(w_i\) 以及价值 \(v_i\) 。检验矿产的流程是：
- 给定 \(m\) 个区间 \([l_i,r_i]\)；
- 选出一个参数 \(W\)；
- 对于一个区间 \([l_i,r_i]\)，计算矿石在这个区间上的检验值 \(y_i\)：
\(y_i=\sum\limits_{j=l_i}^{r_i}[w_j \ge W] \times \sum\limits_{j=l_i}^{r_i}[w_j \ge W]v_j\)
其中 \(j\) 为矿石编号。
这批矿产的检验结果 \(y\) 为各个区间的检验值之和。即：\(\sum\limits_{i=1}^m 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\)。注意：不同区间可能重合或相互重叠。
【输出】
一个整数，表示所求的最小值。
【输入样例】
5 3 15
1 5
2 5
3 5
4 5
5 5
1 5
2 4
3 3
【输出样例】
10
【算法标签】
《洛谷 P1314 聪明的质监员》 #数学# #二分# #前缀和# #NOIP提高组# #2011#
【代码详解】
#include <bits/stdc++.h>
using namespace std;#define int long long // 定义int为long long类型// 变量定义
int n, m, s; // n: 矿石数量, m: 区间数量, s: 目标值
int sn[200005]; // 前缀和数组：满足条件的矿石数量
int sv[200005]; // 前缀和数组：满足条件的矿石价值
int w[200005]; // 矿石重量数组
int v[200005]; // 矿石价值数组
int l[200005], r[200005]; // 每个区间的左右端点
int ans = 1e18; // 存储最小差值，初始化为极大值/*** 检查当前重量阈值W是否满足条件* @param W 当前尝试的重量阈值* @return 是否当前计算值小于等于目标值s*/
bool check(int W)
{// 初始化前缀和数组memset(sn, 0, sizeof(sn));memset(sv, 0, sizeof(sv));// 计算前缀和for (int i = 1; i <= n; i++) {if (w[i] >= W) {sn[i] = sn[i - 1] + 1; // 满足条件的矿石数量sv[i] = sv[i - 1] + v[i]; // 满足条件的矿石价值}else {sn[i] = sn[i - 1];sv[i] = sv[i - 1];}}// 计算所有区间的加权和int y = 0;for (int i = 1; i <= m; i++) {y += (sn[r[i]] - sn[l[i] - 1]) * (sv[r[i]] - sv[l[i] - 1]);}// 更新最小差值ans = min(ans, abs(y - s));return y <= s;
}/*** 二分查找最优的重量阈值* @return 找到的最小差值*/
int find()
{int l = 0, r = 1000000 + 1; // 重量阈值的搜索范围// 二分查找while (l + 1 < r) {int mid = (l + r) / 2;if (check(mid)) {r = mid; // 尝试更小的阈值}else {l = mid; // 需要更大的阈值}}return ans;
}signed main()
{// 输入数据cin >> n >> m >> s;for (int i = 1; i <= n; i++) {cin >> w[i] >> v[i];}for (int i = 1; i <= m; i++) {cin >> l[i] >> r[i];}// 查找并输出结果cout << find() << endl;return 0;
}
// 使用acwing模板二刷
#include <bits/stdc++.h>
using namespace std;#define int long long // 定义int为long long类型
const int N = 200005; // 定义最大矿石数量// 全局变量声明
int n, m, s; // n:矿石数量, m:区间数量, s:目标值
int sn[N], sv[N]; // 前缀和数组：sn记录数量, sv记录价值
int w[N], v[N]; // w:矿石重量数组, v:矿石价值数组
int l[N], r[N]; // 每个区间的左右端点
int ans = 1e18; // 存储最小差值，初始化为极大值/*** 检查函数，验证当前重量阈值W是否满足条件* @param W 当前尝试的重量阈值* @return 返回当前计算值是否小于等于目标值s*/
bool check(int W)
{// 初始化前缀和数组memset(sn, 0, sizeof(sn));memset(sv, 0, sizeof(sv));// 计算前缀和for (int i = 1; i <= n; i++){if (w[i] >= W){sn[i] = sn[i - 1] + 1; // 满足条件的矿石数量sv[i] = sv[i - 1] + v[i]; // 满足条件的矿石价值}else{sn[i] = sn[i - 1];sv[i] = sv[i - 1];}}// 计算所有区间的加权和int y = 0;for (int i = 1; i <= m; i++){y += (sn[r[i]] - sn[l[i] - 1]) * (sv[r[i]] - sv[l[i] - 1]);}// 更新最小差值ans = min(ans, abs(y - s));return y <= s;
}/*** 二分查找函数，寻找最优的重量阈值* @return 返回找到的最小差值*/
int find()
{int l = 0, r = 1000000; // 重量阈值的搜索范围// 二分查找过程while (l < r){int mid = (l + r) >> 1; // 等价于(l + r)/2if (check(mid)){r = mid; // 尝试更小的阈值}else{l = mid + 1; // 需要更大的阈值}}return ans;
}signed main()
{// 输入数据cin >> n >> m >> s;for (int i = 1; i <= n; i++){cin >> w[i] >> v[i];}for (int i = 1; i <= m; i++){cin >> l[i] >> r[i];}// 查找并输出结果cout << find() << endl;return 0;
}
【运行结果】
5 3 15
1 5
2 5
3 5
4 5
5 5
1 5
2 4
3 3
10