Luogu

分析

设 $f(x)$ 为造恰好 $k$ 张光盘的最小花费。感性理解可以发现 $f(x)$ 是一个下凸壳。

考虑 WQS 二分。二分斜率 $m$，求切点相当于最小化 $y$ 轴上的截距，即求出最小的 $f(x)-mx$。

这个最小值的意义就是可以随意造光盘，且每造一张光盘可以赚 $m$ 元时的最小花费（显然它一定非负）。

考虑用堆解决这个问题。

维护一个小根堆，每次将 $a_i$ 插入到堆中，然后将当前的 $b_i$ 与堆顶匹配。然而当前的 $b_i$ 可能不优，所以要再往堆中插入 $-b_i$，这样子以后某个更优的 $b_j$ 如果选到了这个就代表将之前与 $b_i$ 匹配的 $a_k$ 与 $b_j$ 匹配，并舍弃 $b_i$。

$m$ 的话可以一开始将所有的 $b_i$ 都减去 $m$，显然求出来仍是正确的。

另外我们还需要求出最多能造的光盘数以便 check，所以这个过程中堆中的每个元素还要维护一下是 $a_i$ 还是后悔操作。

代码

// ===================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;

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=500000+10;

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

pair<int,ll> f(ll mid) {
    priority_queue<pli,vector<pli>,greater<pli> > Q;
    int cnt=0; ll res=0;
    for (int i=1;i<=n;++i) {
        Q.push(make_pair(a[i],0));
        pli tp=Q.top();
        if (tp.first+b[i]-mid<0) {
            Q.pop(); cnt+=!tp.second,res+=tp.first+b[i]-mid;
            Q.push(make_pair(-b[i]+mid,1));
        }
    }
    return make_pair(cnt,res);
}

int main() {
    n=read(),k=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) {
        int mid=(L+R+1)>>1;
        if (f(mid).first<=k) L=mid;
        else R=mid-1;
    }
    printf("%lld\n",f(L).second+L*k);
    return 0;
}