题目描述

小T 是一名质量监督员,最近负责检验一批矿产的质量。这批矿产共有 n 个矿石,从 1 到 n 逐一编号,每个矿石都有自己的重量 wiw_i 以及价值 viv_i 。检验矿产的流程是:

1 、给定m 个区间 [li,ri][l_i,r_i]

2 、选出一个参数 WW

3 、对于一个区间 [li,ri][l_i,r_i],计算矿石在这个区间上的检验值 yiy_i

yi=j=liri[wjW]×j=liri[wjW]vjy_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

其中 jj 为矿石编号。

这批矿产的检验结果 yy 为各个区间的检验值之和。即:i=1myi\sum\limits_{i=1}^m y_i

若这批矿产的检验结果与所给标准值 ss 相差太多,就需要再去检验另一批矿产。小T 不想费时间去检验另一批矿产,所以他想通过调整参数 WW 的值,让检验结果尽可能的靠近标准值 ss,即使得 sy|s-y| 最小。请你帮忙求出这个最小值。

输入格式

第一行包含三个整数 n,m,s,分别表示矿石的个数、区间的个数和标准值。

接下来的 n 行,每行两个整数,中间用空格隔开,第 i+1 行表示 i 号矿石的重量 wiw_i 和价值 viv_i

接下来的 m 行,表示区间,每行两个整数,中间用空格隔开,第 i+n+1 行表示区间 [li,ri][l_i,r_i] 的两个端点 lil_irir_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%10\% 的数据,有 1n,m101 ≤n ,m≤10

对于 30%30\%的数据,有 1n,m5001 ≤n ,m≤500

对于 50%50\% 的数据,有 1n,m5,0001 ≤n ,m≤5,000

对于 70%70\% 的数据,有 1n,m10,0001 ≤n ,m≤10,000

对于 100%100\% 的数据,有 1 ≤n ,m≤200,000,0<wi,vi1060 < w_i,v_i≤10^60<s10120 < s≤10^{12}1lirin1 ≤l_i ≤r_i ≤n

题目分析

首先来理解下公式的含义。

yi=j=liri[wjW]×j=liri[wjW]vjy_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个矿石的 wiw_i 大于参数 WW 时, [wjW][w_j \ge W] 表达的含义为1,否则为0。

所以公式的意思就是,统计区间 [li,ri][l_i,r_i] 内所有重量大于等于参数W的矿石的个数,得到sw;以及累加区间 [li,ri][l_i,r_i] 内所有重量大于等于参数W的矿石的价值,得到sv 。将两者相乘的乘积就是 yiy_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];
}

yiy_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(wi)W>max(w_i)时,y最小。

这个W的变化过程满足单调性,可以考虑二分答案

我们要求的是sumyS|sum_y - S| 的最小值。

sumy=Ssum_y = S 时,差值最小,为0。

sumy<Ssum_y<S时,要想差值变小,则需要 sumysum_y 的值变大,也就是W 要变小。

sumy>Ssum_y>S时,要想差值变小,则需要 sumysum_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.


( ノ^ω^)ノ゚ 稻 花 香 里 说 丰 年 , 听 取 WA 声 一 片 。(╥╯^╰╥)