题解 P1314 【聪明的质监员】

2018-06-19 18:26:49


【问题描述】

小 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 的绝对值最小。请你帮忙求出这个最小值。

【输入数据】

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

接下来的 nn 行,每行 22 个整数,中间用空格隔开,第 i+1i+1 行表示 ii 号矿石的重量 w_iw i ​ 和价值 v_iv i ​ 。

接下来的 m 行,表示区间,每行 2 个整数,中间用空格隔开,第 i+n+1 行表示区间 [Li,Ri]的两个端点 Li 和 Ri 。注意:不同区间可能重合或相互重叠。

【输出数据】

一个整数,表示所求的最小值。

【输入样例 1】

5 3 15

1 5

2 5

3 5

4 5

5 5

1 5

2 4

3 3

【输出样例 1】

10

【数据范围】

对于 10% 的数据,有 1 ≤n ,m≤101≤n,m≤10 ;

对于 30% 的数据,有 1 ≤n ,m≤5001≤n,m≤500 ;

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

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

对于 100% 的数据,有 1≤ n ,m ≤200,000,0< wi,vi ≤10^6,0< S ≤10^12,1 ≤Li ≤ Ri ≤ n,1 ≤n,m ≤200,000,0< wi,vi ≤10^6,0< S ≤10^12,1≤ Li ≤ Ri ≤n。


只需要二分答案,找离s最近的答案即可,并不难

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define N 200001
#define M 200001
#define ll long long
using namespace std;
int n,m,l[M],r[M],v[N],w[N];
int maxw;
ll ans,tmp,s;
ll sumv[N],sumi[N];
ll judge(int W){
    ll res = 0;
    sumv[0] = sumi[0] = 0ll;
    for(int i = 1;i <= n;i++){
        if(w[i] >= W)sumv[i] = sumv[i - 1] + (ll)v[i],sumi[i] = sumi[i - 1] + 1ll;
        else sumv[i] = sumv[i - 1],sumi[i] = sumi[i - 1];
    }
    for(int i = 1;i <= m;i++)
        res += (sumi[r[i]] - sumi[l[i] - 1]) * (sumv[r[i]] - sumv[l[i] - 1]);
    return res;
}
int main()
{
    scanf("%d %d %lld",&n,&m,&s);
    for(int i = 1;i <= n;i++)
        scanf("%d %d",&w[i],&v[i]),maxw = max(maxw,w[i]);
    for(int i = 1;i <= m;i++)
        scanf("%d %d",&l[i],&r[i]);
    int L = 1,R = maxw;
    while(L <= R){
        int mid = (L + R) / 2;
        tmp = judge(mid);
        if(tmp <= s)R = mid - 1;
        else L = mid + 1;
        if(abs(s - ans) > abs(tmp - s))ans = tmp;
    }
    printf("%lld",abs(ans - s));
    return 0;
}