[NOIP2011 提高组] 聪明的质检员
题目描述
小T
是一名质量监督员,最近负责检验一批矿产的质量。这批矿产共有 \(n\) 个矿石,从 \(1\) 到 \(n\) 逐一编号,每个矿石都有自己的重量 \(w_i\) 以及价值 \(v_i\) 。检验矿产的流程是:
- 给定$ m$ 个区间 \([l_i,r_i]\);
- 选出一个参数 \(W\);
- 对于一个区间 \([l_i,r_i]\),计算矿石在这个区间上的检验值 \(y_i\):
其中 \(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\)。注意:不同区间可能重合或相互重叠。
输出格式
一个整数,表示所求的最小值。
样例 #1
样例输入 #1
5 3 15
1 5
2 5
3 5
4 5
5 5
1 5
2 4
3 3
样例输出 #1
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 < w_i,v_i≤10^6\),\(0 < s≤10^{12}\),\(1 ≤l_i ≤r_i ≤n\) 。
解答过程:
- 枚举每一个\(W\)可能的值,然后对于每一次区间上的检验,首先求出一个前缀数组,再利用前缀数组直接差分来求解区间上产品的价值
- 如果不利用前缀数组的话,这个区间求价值度的时间复杂度就会达到 \(O(n*m)\)
最差情况下,利用前缀和可以把每次查询的时间复杂度由\(O(n)\)变为\(O(1)\)
AC代码
#include <bits/stdc++.h>
using namespace std;
#define MAXN 200009
using i64 = long long;
i64 w[MAXN], l[MAXN], r[MAXN], v[MAXN];
i64 qian[MAXN], num[MAXN];
int main()
{
i64 n, m, s;
scanf("%lld %lld %lld", &n, &m, &s);
i64 w_max;
for (int i = 1; i <= n; i++)
{
scanf("%lld %lld", &w[i], &v[i]);
i == 1 ? w_max = w[i] : w_max = std::max(w_max, w[i]);
}
for (int i = 1; i <= m; i++)
scanf("%lld %lld", &l[i], &r[i]);
auto _find = [&](int W)
{
for (int i = 0; i <= n; i++)
qian[i] = 0, num[MAXN] = 0;
for (int i = 1; i <= n; i++)
{
qian[i] = qian[i - 1] + (w[i] >= W ? v[i] : 0);
num[i] = num[i - 1] + (w[i] >= W ? 1 : 0);
}
i64 ans = 0;
for (int _ = 1; _ <= m; _++)
{
i64 t1 = num[r[_]] - num[l[_] - 1];
i64 t2 = qian[r[_]] - qian[l[_] - 1];
ans += t1 * t2;
}
return ans;
};
i64 _left = 0, _right = w_max;
i64 __MIN__ = LONG_LONG_MAX;
while (1)
{
if (_left > _right)
break;
i64 mid = _left + (_right - _left) / 2;
i64 ans = _find(mid);
__MIN__ = std::min(__MIN__, abs(s - ans));
if (_right == _left)
{
__MIN__ = std::min(__MIN__, abs(s - ans));
break;
}
if (ans < s)
{
_right = mid ;
}
else if (ans > s)
{
_left = mid+1;
}
else
{
__MIN__ = 0;
break;
}
}
std::cout << __MIN__;
return 0;
}
标签:__,10,NOIP2011,检验,i64,聪明,质检员,MAXN,区间
From: https://www.cnblogs.com/cxjy0322/p/18310609