M_sea

洛谷1314 聪明的质检员
题目描述小T 是一名质量监督员,最近负责检验一批矿产的质量。这批矿产共有 n 个矿石,从 1到n 逐一编号,每个矿...
扫描右侧二维码阅读全文
15
2017/10

洛谷1314 聪明的质检员

题目描述

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

  1. 给定m 个区间[Li,Ri];
  2. 选出一个参数 W;
  3. 对于一个区间[Li,Ri],计算矿石在这个区间上的检验值Yi:
    公式

这批矿产的检验结果Y 为各个区间的检验值之和。即:Y1+Y2...+Ym。若这批矿产的检验结果与所给标准值S 相差太多,就需要再去检验另一批矿产。

小T不想费时间去检验另一批矿产,所以他想通过调整参数W 的值,让检验结果尽可能的靠近标准值S,即使得S-Y 的绝对值最小。请你帮忙求出这个最小值。

传送门

算法

二分答案+前缀和即可。

在(0,max(Ri)+1)范围内二分参数W,然后利用前缀和计算Y。

用fv来表示>=参数W的v的前缀和,fs来表示>=参数W的数量的前缀和。
若w[i]>=参数W,则$fv[i]=fv[i-1]+v[i],fs[i]=fs[i-1]+1$;
否则$fv[i]=fv[i-1],fs[i]=fs[i-1]$。

然后直接利用前缀和算出Y。
如果Y-S>0,说明此时选到的矿石过多,需要r=mid。
否则说明选到的矿石过少,需要l=mid+1。

同时在判断时更新答案,即ans=min(ans,|Y-S|)。

最后输出即可。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define ri register int 
#define LL long long
using namespace std;
inline LL labs(LL a) { if (a<0) return -a; else return a; } //long long绝对值
int w[200010],v[200010];
int l[200010],r[200010];
int n,m;
LL S,ans;
int fv[200010],fs[200010]; //fv是>=参数W的v的前缀和,fs是>=参数W的数量的前缀和 
inline bool BIG(int k) //判断是否Y>S
{
    memset(fv,0,sizeof(fv));
    memset(fs,0,sizeof(fs)); //清空数组
    for (ri i=1;i<=n;i++) { //计算前缀和
        if (w[i]>=k) {
            fv[i]=fv[i-1]+v[i];
            fs[i]=fs[i-1]+1;
        }
        else {
            fv[i]=fv[i-1];
            fs[i]=fs[i-1];
        }
    }
    LL Y=0;
    for (ri i=1;i<=m;i++) { //计算Y
        LL tv=fv[r[i]]-fv[l[i]-1];
        LL ts=fs[r[i]]-fs[l[i]-1];
        Y=Y+(tv*ts);
    }
    ans=min(ans,labs(Y-S)); //更新答案
    if (Y-S>0) return true;
    else return false;
}
int main()
{
    scanf("%d%d%lld",&n,&m,&S);
    LL L=0,R=-1;
    for (ri i=1;i<=n;i++) { //输入
        scanf("%d%d",&w[i],&v[i]);
        R=max(R,(LL)w[i]);
    }
    for (ri i=1;i<=m;i++) scanf("%d%d",&l[i],&r[i]); //输入
    L=0; R++; ans=1000000000000000000; //初始化左右界和答案
    while (L<R) { //二分答案
        LL mid=(L+R)>>1; //计算中点
        if (!BIG(mid)) R=mid; //矿石少了,所以要减
        else L=mid+1; //矿石多了,所以要加 
    }
    printf("%lld\n",ans); //输出
    return 0;
}
最后修改:2018 年 11 月 09 日 04 : 23 PM

发表评论