洛谷1314 聪明的质检员

Luogu

分析

通过人类智慧可以知道,随着 $W$ 的增大,检验结果 $Y$ 是单减的。

于是我们只要二分出最大的 $Y_W\geq S$ 的 $W$,然后在 $Y_W-S$ 和 $S-Y_{W+1}$ 中取个 $\min$ 就好了。

算 $Y_W$ 时预处理前缀和即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

int n,m,S;
int w[N],v[N],l[N],r[N];
int cnt[N],sum[N];

inline int calc(int W) {
    for (re int i=1;i<=n;++i) {
        cnt[i]=cnt[i-1],sum[i]=sum[i-1];
        if (w[i]>=W) ++cnt[i],sum[i]+=v[i];
    }
    int res=0;
    for (re int i=1;i<=m;++i)
        res+=(cnt[r[i]]-cnt[l[i]-1])*(sum[r[i]]-sum[l[i]-1]);
    return res;
}

signed main() {
    n=read(),m=read(),S=read();
    for (re int i=1;i<=n;++i) w[i]=read(),v[i]=read();
    for (re int i=1;i<=m;++i) l[i]=read(),r[i]=read();
    int L=1,R=1e6;
    while (L<R) {
        int mid=(L+R+1)>>1;
        if (calc(mid)>=S) L=mid;
        else R=mid-1;
    }
    printf("%lld\n",min(calc(L)-S,S-calc(L+1)));
    return 0;
}
最后修改:2019 年 11 月 04 日 09 : 30 PM

发表评论