题目
小 T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有 \(n\) 个矿石，从 \(1\) 到 \(n\) 逐一编号，每个矿石都有自己的重量 \(w_i\) 以及价值 \(v_i\) 。检验矿产的流程是：
1 、给定 \(m\) 个区间 \([l_i,r_i]\)；
2 、选出一个参数 \(W\)；
3 、对于一个区间 \([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|\) 最小。请你帮忙求出这个最小值。
解析
这是一道比较清晰明了的二分答案。
可以看出整个式子的自变量是 \(W\)，因变量是此时得到的 \(y\)。
那么就来判断是否可以运用二分来解，首先判断单调性：
当 \(W\) 比最轻的矿石质量还小时，所有的矿石都可以参与运算，计算出来的 \(y\) 必定最大。
当 \(W\) 比最重的矿石质量还大时，所有的矿石都不能参与运算，计算出来的 \(y\) 必定最小。
因此，\(W\) 越小，参与计算的数就越多，\(y\) 也就越大。
所以单调性出来了，我们就可以在区间内通过枚举 \(W\) 来得到答案了。
然后就 \(TLE\) 了……
优化
查看代码发现，二分部分肯定是不会有什么超时的地方，那就是 check 函数的问题了。
发现在每次计算过程中由于重复计算造成了大量的浪费，于是考虑用前缀和优化。
使用 sum_n[i] 来表示区间中合格部分数量，sum_v[i] 来记录区间中合格部分价值。
最后进行计算。
#include<iostream>
#include<algorithm>
#include<cstdio>
#define int long long
using namespace std;
int n,m,s;
int w[200500],v[200500];
int l[200500],r[200500];
int sum_n[200500],sum_v[200500];
long long ans = 0;
void init()
{
scanf("%lld%lld%lld",&n,&m,&s);
for(int i = 1;i <= n; i++)
scanf("%lld%lld",&w[i],&v[i]);
for(int i = 1;i <= m; i++)
scanf("%lld%lld",&l[i],&r[i]);
return ;
}
long long check(int W)
{
long long ans = 0;
for(int i = 1;i <= n; i++)
{
if( W > w[i] )// 要用前缀和，不然会炸掉！！！
{
sum_n[i] = sum_n[i-1];
sum_v[i] = sum_v[i-1];
}
else
{
sum_n[i] = sum_n[i-1] + 1;
sum_v[i] = sum_v[i-1] + v[i];
}
}
for(int i = 1;i <= m; i++)
{
long long a,b;
a = sum_v[r[i]] - sum_v[l[i]-1];
b = sum_n[r[i]] - sum_n[l[i]-1];
ans += a*b;
}
return ans;
}
long long _abs(long long a)
{
if( a > 0 )
return a;
return -a;
}
signed main()
{
init();
int left = 0,right = 1000000,mid;
while( left <= right )
{
mid = (left + right)>>1;
if( check(mid) > s )
left = mid + 1;
else
right = mid - 1;
}
ans = _abs(check(left) - s);
if( _abs(check(right) - s) < ans )
ans = _abs(check(right) - s);
printf("%lld",ans);
return 0;
}
总结
题总体来说并不算难，但细节仍需要注意。
例如在考试中，就很有可能会忘记前缀和优化的问题，导致失去 30 分。
还有一直存在的 long long 的问题，同样会影响数十分。
要注重时间复杂度，重视算法的优化。做题时一定要每道题计算时间复杂度，不然考场追悔莫及。
标签：int,题解,sum,质监,矿石,200500,long,P1314,检验 From： https://www.cnblogs.com/JXYBJ/p/congmingdezhijianyuan.html