【LG P1314】聪明的质监员

这个题很明显的二分枚举,但是还有一个前缀和有点坑人。

这题题其实点不多,就两个关键点。

二分的判断

可以看到:在W取0时,所有的区间内的矿石都可以选上,而在W大于最大的质量时,所有的矿石都选不上。

然后简单算一下就发现:W越大,矿石选的越少,W越小,矿石选的越多。

所以,随着W增大,Y值减小。

所以,二分的判断条件出来了:

当 \(Y>s\) 时,需要增大 \(W\) 来减小 \(y\),从而 \(|W-s|\) 变小;

当 \(Y=s\) 时,\(|Y-s|=0\);

当 \(Y<s\) 时,需要减小 \(W\) 来增大 \(Y\) ,从而 \(|Y-s|\)变大。

前缀和

我们在计算一个区间的和时(虽然这里是两个区间和再相乘,但没关系),通常是用前缀和的方法来缩减时间,直接模拟是 \(n^2\) 的,而前缀和成了 \(2n\),大大的优化了时间。

很显然:

在 \(w_i>=W\) 时这个 \(i\) 矿石会在统计里(若 \(<W\) 就不管它了直接 \(pre_i=pre_{i-1}\)),矿石价值和是:\(pre_v[i]=pre_v[i-1]+v[i]\),前面的和加上当前这一个 \(i\) 矿石;矿石数量和是:\(pre_n[i]=pre_n[i-1]+1\),数量加 \(1\) 嘛。然后最后算的时候用右端点 \(r-\)(左端点 \(l-1\))就可以了。

代码

#include<bits/stdc++.h>
using namespace std;
using LL=long long;
const LL N=2e5+5;
LL n,m,s,w[N],v[N],l[N],r[N],sum_n[N],sum_v[N],sum;
bool check(int W) {
    LL y=0;
    sum=0,memset(sum_n,0,sizeof(sum_n)),memset(sum_v,0,sizeof(sum_v));
    for(int i=1; i<=n; i++) {
        if(w[i]>=W) {
            sum_n[i]=sum_n[i-1]+1,sum_v[i]=sum_v[i-1]+v[i];
        } else {
            sum_n[i]=sum_n[i-1],sum_v[i]=sum_v[i-1];
        }
    }
    for(int i=1; i<=m; i++) {
        y+=(sum_n[r[i]]-sum_n[l[i]-1])*(sum_v[r[i]]-sum_v[l[i]-1]);
    }
    sum=llabs(y-s);
    return y>s;
}
int main() {
    scanf("%lld %lld %lld",&n,&m,&s);
    LL minn=LLONG_MAX>>1,maxn=0;
    for(int i=1; i<=n; i++) {
        scanf("%lld %lld",w+i,v+i),minn=min(minn,w[i]),maxn=max(maxn,w[i]);
    }
    for(int i=1; i<=m; i++) {
        scanf("%lld %lld",l+i,r+i);
    }
    LL left=minn-1,right=maxn+1,ans=LLONG_MAX>>1;
    while(left<=right) {
        LL mid=(left+right)>>1;
        if(check(mid)) {
            left=mid+1;
        } else {
            right=mid-1;
        }
        ans=min(ans,sum);
//        printf("%lld %lld %lld\n",right,mid,left);//Debug
    }
    printf("%lld",ans);
    return 0;
}

参考资料

题解 P1314 【聪明的质监员】 - 人殇物已非 的博客 - 洛谷博客 (luogu.com.cn)

上一篇:从javascript代码解析过程理解执行上下文与作用域提升


下一篇:函数和闭包