题目描述
小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|$ 最小。请你帮忙求出这个最小值。
输入格式
第一行包含三个整数 n,m,s,分别表示矿石的个数、区间的个数和标准值。
接下来的 n 行,每行两个整数,中间用空格隔开,第 i+1 行表示 i 号矿石的重量 $w_i$ 和价值 $v_i$。
接下来的 m 行,表示区间,每行两个整数,中间用空格隔开,第 i+n+1 行表示区间 $[l_i,r_i]$ 的两个端点 $l_i$ 和 $r_i$。注意:不同区间可能重合或相互重叠。
输出格式
一个整数,表示所求的最小值
输入输出样例
输入#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$。
题目分析
首先来理解下公式的含义。
$$ 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个矿石的 $w_i$ 大于参数 $W$ 时, $[w_j \ge W]$ 表达的含义为1,否则为0。
所以公式的意思就是,统计区间 $[l_i,r_i]$ 内所有重量大于等于参数W的矿石的个数,得到sw
;以及累加区间 $[l_i,r_i]$ 内所有重量大于等于参数W的矿石的价值,得到sv
。将两者相乘的乘积就是 $y_i$ 。
对于区间求和问题,可以采用前缀和的思想进行加速。
维护前缀和数组
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];
}
求 $y_i$ 的值
y[i]=(sw[r[i]]-sw[l[i]-1]) * (sv[r[i]]-sv[l[i]-1]);
通过观察,可发现,参数W
定的越小,满足条件的石头就越多,y
也就越大,W
为0时,y
最大;而参数W
定的越大,满足条件的是否就越少,y
也就越小,$W>max(w_i)$时,y
最小。
这个W
的变化过程满足单调性,可以考虑二分答案。
我们要求的是$|sum_y - S|$ 的最小值。
当$sum_y = S$ 时,差值最小,为0。
当$sum_y<S$时,要想差值变小,则需要 $sum_y$ 的值变大,也就是W
要变小。
当$sum_y>S$时,要想差值变小,则需要 $sum_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;
}