P4694 Raper
磕 T2 去了，没想到这题部分分是简单费用流。
直接上图，\((S\rightarrow i,1,a_i),(i \rightarrow T',1,b_i)\)，不解释。
\((T' \rightarrow T,k,0)\)，限流。
\((i\rightarrow i+1,inf,0)\)，表示保留到下一天选。
这样就有 56 的高分了。
然后就是模拟费用流了。
直接模拟费用流很难做，其实有更简单的方法。
设 \(f(x)\) 表示生产 \(x\) 张光盘的费用，可以发现这是个凸函数。于是可以用 wqs 二分。
对于这题，显然生产 0 张费用最低。那么让它能生产 \(k\) 张呢？
我们可以二分一个 \(c\)，流量每多 \(1\) 就能加上 \(c\)，相当于给个奖励。（本题 \(c\leq 0\)）。
这样就没有限流的必要了，原图简化为这样：
从 \(n\sim 1\) 依次考虑一条路径。
若是一条流向 \(T\) 的路径，那么一定是选一条 \((b_j,1),j\geq i\)，其中 \(b_j\) 最小 的边流向 \(T\)。
用一个优先队列维护最小的 \(b_j\)，如果这条路径费用 \(\leq 0\)，直接流过去，并加入反边（后文解释反边加入什么）。
考虑一条流向 \(S\) 的路径，有两种情况（假设当前考虑点 1）。
这个好办，对于一个 \(i\)，如果从 \(S\) 流出去了，那么加入费用为 \(-a_i-c\) 的反边。\(-c\) 因为流量 \(-1\)。
还有一种情况：
注意蓝色的边显然费用和非负，那么走蓝边对应的正边直接从 \(S\) 流向 \(T\) 费用和为非正，那之前为什么不直接流过去？所以这种情况不存在。
复杂度 \(O(n\log ^2 n)\)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
int n,k,ans,cnt,a[N],b[N];
struct node{
int c,w;
bool operator<(const node&x)const{
return c==x.c?w<x.w:c>x.c;
}
};
int f(int c)
{
priority_queue<node> q;
ans=cnt=0;
for(int i=n;i;i--)
{
q.push({b[i],1});
if(a[i]+q.top().c+c<=0)
{
ans+=a[i]+q.top().c+c;
if(q.top().w) cnt++;
q.pop();
q.push({-a[i]-c,0});
}
}
return cnt>=k;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
int l=-2e9,r=0,c=0;
while(l<=r)
{
int mid=l+r>>1;
if(f(mid)) c=mid,l=mid+1;
else r=mid-1;
}
f(c);
cout<<ans-k*c<<'\n';
}