【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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82