【题解】聪明的质监员(前缀和+二分答案)
【题解】聪明的质监员(前缀和+二分答案)
题目描述
小T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有 n 个矿石，从 1 到 n 逐一编号，每个矿石都有自己的重量
以及价值
。检验矿产的流程是：
1 、给定m 个区间
；
2 、选出一个参数 W；
3 、对于一个区间
，计算矿石在这个区间上的检验值
：
其中 j为矿石编号。
这批矿产的检验结果 y 为各个区间的检验值之和。即：
若这批矿产的检验结果与所给标准值 s 相差太多，就需要再去检验另一批矿产。小T 不想费时间去检验另一批矿产，所以他想通过调整参数 W 的值，让检验结果尽可能的靠近标准值 s，即使得 ∣s−y∣最小。请你帮忙求出这个最小值。
输入格式
第一行包含三个整数 n,m,s，分别表示矿石的个数、区间的个数和标准值。
接下来的 n 行，每行两个整数，中间用空格隔开，第 i+1 行表示 i 号矿石的重量
和价值
。
接下来的 m 行，表示区间，每行两个整数，中间用空格隔开，第 i+n+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。
数据范围
题目分析
首先来理解下公式的含义。
当第j个矿石的
大于参数 W 时,
表达的含义为1,否则为0。
所以公式的意思就是，统计区间
内所有重量大于等于参数W的矿石的个数，得到sw；以及累加区间
内所有重量大于等于参数W的矿石的价值，得到sv 。将两者相乘的乘积就是
。
对于区间求和问题，可以采用前缀和的思想进行加速。
维护前缀和数组
for(int i=1;i<=n;i++){
int k=(w[i]>=W);
sw[i]=sw[i-1]+k;
sv[i]=sv[i-1]+k*v[i];
}求 yiy_iyi 的值
y[i]=(sw[r[i]]-sw[l[i]-1]) * (sv[r[i]]-sv[l[i]-1]);通过观察，可发现，参数W定的越小，满足条件的石头就越多，y也就越大，W为0时，y最大；而参数W定的越大，满足条件的是否就越少，y也就越小，
时，y最小。
这个W的变化过程满足单调性，可以考虑二分答案。
我们要求的是
的最小值。
二分答案框架
while(L<=R){
mid=(L+R)/2;
...
if(sum==S){
break;
}else if(sum<S){
R=mid-1;
}else {
L=mid+1;
}
}实现代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=2e5+5;
typedef long long ll;
int w[N],v[N];
int n,m,l[N],r[N];
ll s,ans;
ll sw[N],sv[N];
ll cal(int mid){
//清空前缀和数组
memset(sw,0,sizeof(sw));
memset(sv,0,sizeof(sv));
//维护前缀和数组
for(int i=1;i<=n;i++){
int k=(w[i]>=mid);
sw[i]=sw[i-1]+k;
sv[i]=sv[i-1]+k*v[i];
}
ll sum=0;
//累加yi
for(int i=1;i<=m;i++){
sum+=(sw[r[i]]-sw[l[i]-1])*(sv[r[i]]-sv[l[i]-1]);
}
return sum;
}
int main(){
scanf("%d%d%lld",&n,&m,&s);//输入矿石数量 区间个数 标准值
ans=s;//初始化 最小差值
int L=0,R=0;// 参数W 的范围
for(int i=1;i<=n;i++){
scanf("%d%d",&w[i],&v[i]);//输入矿石重量 和 价值
R=max(R,w[i]);//更新最大重量
}
for(int i=1;i<=m;i++){
scanf("%d%d",&l[i],&r[i]);//输入检查的区间
}
R++;//W的最大范围加1 ， 当比最大值大时，所有矿石都不满足条件
int mid;
while(L<=R){//二分答案框架
mid=(L+R)>>1;//求中间值
ll sum=cal(mid);//计算mid位参数下的sum_y
ans=min(ans,abs(s-sum));//更新最小差值
if(sum==s){//总和 == s 达到最小差值0 ，直接结束
break;
}else if(sum<s){
//sum<s时，要想差值变小，则需要 sum 的值变大,则W要变小
R=mid-1;
}else{
//sum>s时，要想差值变小，则需要 sum 的值变小,则W要变大
L=mid+1;
}
}
cout<<ans;//输出最小差值
return 0;
}Q.E.D.
腾讯云开发者
