题解：P4694 [PA 2013] Raper

LastKismet · 2025-07-07 20:18:30 · 题解

Sol

WQS 二分套反贪。

考虑如果没有光盘张数限制，那么就是一个经典的反贪问题（我知道一个都不选最优，请先忽略这一点……），在 i 天的 A 工厂与 j 天的 B 工厂加工的光盘将会产生 a_i+b_j 的贡献，每次 b 尝试贪心选最小的 a 更新答案即可。如何反悔呢？选完一个 b_j 后往堆里推一个 -b_j 即可。这部分不理解建议先去学一下反悔贪心。

如何处理限制呢？很典型的 WQS 二分啊。记 f_i 为造 i 个光盘的代价，(i,f_i) 显然是凸的，所以直接上 WQS 二分即可，通俗地理解就是二分生产一张光盘额外产生的价值。没了。

WQS 二分时有几个坑点，一个是典型的要处理好多点共线的情况，我这里设定要最小化选的个数，那么对于两个代价相同的选择，就要优先选不会更加点数的选项（也就是优先反悔）。如果要最大化选的个数同理。最后消除 \Delta 影响时记得使用给出的 k，如果不理解可以参考这里的 WQS 二分讲解。

Code

int n,k;
ll a[N],b[N];

inline pli check(ll dlt){
    ll res=0;int cnt=0;
    lrheap<pli> pq;
    rep(i,1,n){
        pq.push({a[i],1});
        if(dlt+b[i]+pq.top().fir<0){
            res+=dlt+b[i]+pq.top().fir;
            cnt+=pq.top().sec;
            pq.pop();
            pq.push({-dlt-b[i],0});
        }
    }
    return {res,cnt};
}

inline void Main(){
    read(n,k);
    rep(i,1,n)read(a[i]);
    rep(i,1,n)read(b[i]);
    ll l=-2e9,r=0;
    while(l<r){
        ll m=l+r>>1;
        if(check(m).sec<=k)r=m;
        else l=m+1;
    }
    put(check(l).fir-k*l);
}