ARC125E Snack

题意：有 $n$ 种零食，每种零食有 $a_i$ 片，有 $m$ 个小孩，每种小孩每种零食最多拿 $b_i$ 片（$b_i$ 只和小孩相关），一共不能超过 $c_i$ 片。问最多能拿走的零食片。$n, m\leq 2\times 10 ^ 5$，$a_i, c_i\leq 10 ^ {12}$，$b_i\leq 10 ^ 7$。

首先容易得到一个网络流的做法：$S$ 向每一个零食连边，流量为 $a_i$；零食 $i$ 想小孩 $j$ 连边，流量为 $b_j$；小孩 $j$ 向 $T$ 连边，流量为 $c_j$。

但是这这种办法的空间过于庞大，无法建出网络流。考虑我们模拟网络流的过程，尝试找到最大流。

首先一个性质就是将最大流转化为最小割。我们考虑左部点中有 $x$ 个与 $S$ 联通，按照割的定义，右边的 $m$ 个点要么和 $T$ 割开，要么和左边的 $x$ 个点都割开。前面一种方案的代价是 $c_j$，后面一种方案的代价是 $x\times b_j$。这两个需要取 $\min$，那么我们考虑一个分段的一次函数，分别维护斜率和截距即可。

容易发现后面的贡献只和 $x$ 的大小有关，和左边到底哪些和 $S$ 联通无关。于是我们直接对整个 $a$ 数组排序，选取前 $n - x$ 个与 $S$ 断开即可。

除开排序，我们很容易用前缀和在 $O(n + m)$ 的时间内解决原问题。

int main()
{
	std::cin >> n >> m;
	for (int i = 1; i <= n; ++ i) scanf("%lld", a + i);
	for (int i = 1; i <= m; ++ i) scanf("%lld", b + i);
	for (int i = 1; i <= m; ++ i) scanf("%lld", c + i);
	std::sort(a + 1, a + n + 1);
	for (int i = 1; i <= m; ++ i) {
		k[1] += b[i];
		if ((t = (c[i] + b[i] - 1) / b[i]) <= n)
			k[t] -= b[i], st[t] += c[i];
	}
	for (int i = 1; i <= n; ++ i) k[i] += k[i - 1], st[i] += st[i - 1];
	auto get = [&](int s) { return k[s] * s + st[s]; };
	LL res = 5e18, sum = 0;
	for (int i = 0; i <= n; ++ i)
		res = std::min(res, get(n - i) + (sum += a[i]));
	std::cout << res << '\n';
	return 0;
}