聪明的质检员
描述
小 T 是一名质量监督员,最近负责检验一批矿产的质量。这批矿产共有n个矿石,从1到n逐一编号,每个矿石都有自己的重量wi以及价值vi。检验矿产的流程是:
1、给定m个区间[Li,Ri];
2、选出一个参数W;
3、对于一个区间[Li,Ri],计算矿石在这个区间上的 检验值$Y_i$:
\[Y_i=(\sum_j {1}) \times(\sum_j v_j) ,j \in [L_i,R_i] \land \: w_i \geqslant W\]其中 $j$ 为矿石编号
这批矿产的 检验结果Y 为各个区间的检验值之和 。即:
\[Y = \sum _{i=1} ^m Y_i\]
若这批矿产的 检验结果 与所给标准值S相差太多,就需要再去检验另一批矿产。小T不想费时间去检验另一批矿产,所以他想通过调整参数W的值,让 检验结果 尽可能的靠近标准值S,即使得 S-Y 的绝对值最小。请你帮忙求出这个最小值。
格式
输入格式
第一行包含三个整数n,m,S,分别表示矿石的个数、区间的个数和标准值。
接下来的n行,每行2个整数,中间用空格隔开,第i+1行表示i号矿石的重量wi和价值vi 。
接下来的m行,表示区间,每行2个整数,中间用空格隔开,第i+n+1行表示区间[Li,Ri]的两个端点Li和Ri。 注意:不同区间可能重合或相互重叠。
输出格式
输出只有一行,包含一个整数,表示所求的最小值。
样例1
样例输入1
5 3 15
1 5
2 5
3 5
4 5
5 5
1 5
2 4
3 3#include <set>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm> const int MAXN=;
const long long INF=0x7FFFFFFFFFFFFFFFll; int n;
int m;
long long S;
int L[MAXN];
int R[MAXN];
long long maxw;
long long w[MAXN];
long long v[MAXN];
long long ans=INF;
long long sum[MAXN];
long long count[MAXN]; long long Y(int);
void Initialize(); int main(){
Initialize();
int l=;
int r=maxw;
while(l<=r){
int mid=(l+r)/;
long long tmp=Y(mid);
ans=std::min(ans,std::abs(tmp-S));
if(tmp<S)
r=mid-;
else
l=mid+;
}
printf("%lld\n",ans);
return ;
} long long Y(int W){
// fprintf(stderr, "W=%d\n", W);
long long ret=;
memset(sum,,sizeof(sum));
memset(count,,sizeof(count));
for(int i=;i<=n;i++){
sum[i]=sum[i-];
count[i]=count[i-];
if(w[i]>=W){
sum[i]+=v[i];
count[i]++;
}
// fprintf(stderr, "sum[%d]=%lld ,cnt=%lld\n", i,sum[i],count[i]);
}
for(int i=;i<m;i++){
ret+=(sum[R[i]]-sum[L[i]-])*(count[R[i]]-count[L[i]-]);
}
// fprintf(stderr, "ret=%lld\n", ret);
return ret;
} void Initialize(){
freopen("qc.in","r",stdin);
freopen("qc.out","w",stdout);
scanf("%d%d%lld",&n,&m,&S);
for(int i=;i<=n;i++){
scanf("%lld%lld",w+i,v+i);
maxw=std::max(maxw,w[i]);
}
for(int i=;i<m;i++){
scanf("%d%d",L+i,R+i);
}
}Backup