链接:https://www.luogu.com.cn/problem/P4694
题目描述:有\(k\)个光盘要在\(n\)天之内加工完毕.有\(2\)个工厂\(A,B\),每一个光盘要先在\(A\)工厂加工,再在\(B\)工厂加工,且第\(i\)天在\(A\)工厂,第\(j\)天在\(B\)工厂加工的代价为\(A_{i}+B_{j}\),每一天只能在一个工厂加工,求加工最小代价.
链接:观察题目很像老鼠进洞,考虑先建出费用流模型:
先拆点,考虑连以下几条边:
连\((s',s)\),流量为\(k\),费用为\(0\)
\((s,i)\),流量为\(1\),费用为\(a_{i}\)
\((i',t)\),流量为\(1\),费用为\(b_{i}\)
对于每一个点\(i\),向其右边\(j\)的对应点\(j'\)连边,流量为\(1\),费用为\(0\).
观察到以下流:
\(1.s'->s->i->j'->t\),即选\(i<=j'\)的\(A_{i}+B_{j}\)的最大对
\(2.s'->s->u->j'->i->v'->t\),即\(u>=v'\)的\(A_{u}+B_{v}\)的最大对,但要选过在\(v\)左边的\(1\)与在\(u\)右边的\(1\).
这个可以堆\(+\)线段树维护,但卡不过.
可以考虑如何将\(k\)处理掉,使堆模拟费用流时可以调整顺序做,发现\(ans\)是一个关于\(k\)的凸函数,所以可以\(wqs\)二分,然后这时堆模拟费用流就可以静态做了,此时只要一个堆就行了.
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
__int128 res;
long long first=0,ans,last=2e9,mid,k,n,a[500001],b[500001];
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9')
c=getchar();
while ('0'<=c&&c<='9')
{
sum=sum*10+c-'0';
c=getchar();
}
return sum;
}
struct reads
{
long long data,op;
bool operator < (const reads &a)const
{
return data>a.data;
}
};
reads tmp;
reads make_reads(long long x,long long y)
{
tmp.data=x;
tmp.op=y;
return tmp;
}
int solve(int p)
{
long long u=0;
reads top;
res=0;
priority_queue<reads>q;
for (int i=1;i<=n;++i)
{
q.push(make_reads(a[i],1));
top=q.top();
q.pop();
if (top.data+b[i]-p>=0)
{
q.push(top);
continue;
}
else
{
res+=(top.data+b[i]-p);
q.push(make_reads(-b[i]+p,0));
u+=top.op;
}
}
return u;
}
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();
if (k==n)
{
for (int i=1;i<=n;++i)
ans+=(a[i]+b[i]);
printf("%lld\n",ans);
return 0;
}
while (first<=last)
{
mid=(first+last)/2;
if (solve(mid)<=k)
{
first=mid+1;
ans=max(ans,mid);
}
else
last=mid-1;
}
solve(ans);
printf("%lld\n",res+ans*k);
return 0;
}