题解 CF802O April Fools' Problem (hard)

· · 题解

经典 k 道题，一眼 wqs 二分。

于是可以抛开这个条件，再来看这道题。

发现我们每次决策的时候可以在打印的时候考虑，打印时考虑打印哪天准备的题目。贪心地来讲，我们一定会选择当前准备+打印总花费最少的题目。

进一步而言，对于每一次打印，我们一定会挑选之前准备花费最少且准备+打印总花费为非正数的题目进行打印。但是这显然还不够。

很显然的反例是，之前准备花费最小的题目在最优情况下，本来应该被后面的打印挑走，却被前面的打印先挑走了。这显然是不行的。

于是考虑反悔，用一个小根堆维护之前的所有决策，每次取出价格最低的决策，将当前打印的花费加上决策花费后，如果总花费为非正数，则先选择该决策。又由于：

a_i+b_j-b_j+b_k=a_i+b_j+(-b_j+b_k)

于是把当前打印的花费的相反数加入堆中，供以后反悔使用即可。

还需要特别注意的一点是，由于 wqs 二分时应尽量多选择物品，所以当正常选的决策和反悔的决策花费相同时，我们应该优先选择正常选的决策，使得物品数更多，防止斜率相同的情况发生而无法处理。

剩下的基本就是板子了。代码很短。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5;
ll n,m,a[N],b[N],ans,sum,now;
struct node{
    ll w;
    bool pd;
    node (ll w=0,bool pd=0)
        :w(w),pd(pd){}
    bool operator <(const node&x) const{
        return (w^x.w)?w>x.w:pd<x.pd;
    }
};
int read(){
    int w=0,fh=1;
    char ch=getchar();
    while (ch>'9'||ch<'0'){
        if (ch=='-') fh=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        w=(w<<3)+(w<<1)+(ch^48);
        ch=getchar();
    }
    return w*fh;
}
bool check(ll x){
    sum=now=0;
    priority_queue<node> q;
    while (!q.empty()) q.pop();
    for (int i=1;i<=n;i++){
        q.push(node(a[i]-x,1));
        node s=q.top();
//      printf("%lld %lld\n",1ll*i,s.w);
        if (s.w+b[i]<=0){
            sum+=s.w+b[i];
            now+=s.pd;
            q.pop();
            q.push(node(-b[i],0));          
        }
    }
    return now>=m;
}
int main(){
    n=read(),m=read();
    for (int i=1;i<=n;i++) a[i]=read();
    for (int i=1;i<=n;i++) b[i]=read();
    ll l=0,r=2e9;
    while (l<=r){
        ll mid=l+r>>1;
        if (check(mid)) r=mid-1,ans=sum+m*mid;
        else l=mid+1;
    }
    printf("%lld\n",ans);
    return 0;
}