【CF802O】April Fools‘ Problem (hard)（wqs二分，模拟费用流，老鼠进洞）

如果没有恰好为 \(k\) 的限制的话是个老鼠进洞的经典模型。

加上恰好为 \(k\) 的限制后考虑使用 wqs 二分，因为费用流每次增广出来的费用是单调不降的。即如果设 \(g(k)\) 表示总流量恰好为 \(k\) 的最小花费，那么必有 \(g(k)-g(k-1)\le g(k+1)-g(k)\)，且 \((k,g(k))\) 这些点构成一个凸壳。

wqs 二分的大概思路是：首先要求在没有 \(k\) 的限制下原问题能够快速解决。然后对于一个斜率 \(c\)，发现我们能快速求出斜率为 \(c\) 的直线与凸壳相切在哪个点上，因为经过点 \((k,g(k))\) 的斜率为 \(c\) 的直线在 \(y\) 轴的截距恰好就是 \(g(k)-ck\)，代表的意义就是每多 \(1\) 的流量就要多花费 \(c\) 的额外代价，那么我们在这个条件下跑一次没有限制的原问题即可。然后由于这是个凸壳，所以斜率可以二分。

#include<bits/stdc++.h>

#define N 500010
#define ll long long
#define pii pair<int,int>
#define mk(a,b) make_pair(a,b)

using namespace std;

inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}

struct data
{
	int a;
	bool opt;
	data(){};
	data(int _a,bool _opt){a=_a,opt=_opt;}
	bool operator < (const data &b) const
	{
		if(a==b.a)
		{
			if(opt==b.opt) return 0;
			return b.opt;
		}
		return a>b.a;
	}
};

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

priority_queue<data>q;

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();
	int l=0,r=2e9,c=-1;
	ll inter;
	while(l<=r)
	{
		int mid=(0ll+l+r)>>1ll;
		int nk=0;
		ll gk=0;
		while(!q.empty()) q.pop();
		for(int i=1;i<=n;i++)
		{
			q.push(data(a[i]-mid,1));
			data minn=q.top();
			if(minn.a+b[i]<=0)
			{
				q.pop();
				nk+=minn.opt;
				gk+=0ll+minn.a+b[i];
				q.push(data(-b[i],0));
			}
		}
		if(nk>=k)
		{
			c=mid,inter=gk;
			r=mid-1;
		}
		else l=mid+1;
	}
	printf("%lld\n",inter+1ll*c*k);
	return 0;
}

原文地址：http://www.cnblogs.com/ez-lcw/p/16837310.html