聪明的质检员

聪明的质检员

小鱼干

2024 年 03 月 06 日

612 次浏览

1 条评论

2049字数

程序算法

题目描述

小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

输出#1

说明/提示

输入输出样例说明

当 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;
}

聪明的质检员