ARC125E Snack

tony102

2021 年 10 月 30 日

1603 次浏览

暂无评论

968字数

题解

[Link](https://atcoder.jp/contests/arc125/tasks/arc125_e)

## Sol

首先暴力最大流肯定很容易搞出来，跑 $10^4$ 级别应该差不多？

考虑模拟最大流，因为最大流可能很大，因此把最大流换成最小割，来考虑割会有什么样的效果。

![5xPRwq.png](https://tony102.com/usr/uploads/2021/10/790504276.png)

第二列点就代表零食，第三列就是小朋友。

现在考虑割，割从源点出发到第二列点的边，对最小割是没有影响的。因为第二列到第三列仍然没有发生改变，贡献给答案的只有 $b_j, c_j$，$a_i$ 总共有多少流出去就行了。假如 $a_i$ 割了 $k$ 条边，那么每次取的就是 $\min {((n-k)b_j, c_j)}$ 。这样就存在一个分界点 $k$，前面的都是 $(n-k)b_j$，后面的全部都选 $c_j$。

具体怎么确定选啥，现在是要 $(n-k) b_j > c_j$，只要 $\frac{b_j}{c_j} > \frac{1}{n-k}$  即 $\frac{c_j}{b_j} > n - k$，先默认 $k=0$。因为分界点每次我们都需要枚举，所以每次取  $\frac{b_j}{c_j} \leq k$ 的位置即可。

## Code

```cpp
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int SIZE = 2e5 + 5;

int n, m;
int b[SIZE]; LL s[SIZE], a[SIZE], c[SIZE];
vector < int > flow[SIZE];

namespace GTR {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	template < class T > 
	inline T read() {
		T a = 0, b = 1, c = fetch();
		while (c < 48 || c > 57) b ^= c == '-', c = fetch();
		while (c >= 48 && c <= 57) a = a * 10 + c - 48, c = fetch();
		return b ? a : -a;
	}
} using GTR::read;

int main() {
    n = read <int> (), m = read <int> (); LL sumb = 0;
    for (int i = 1; i <= n; ++ i) a[i] = read <LL> (), s[i] = s[i - 1] + a[i];
    for (int i = 1; i <= m; ++ i) b[i] = read <int> (), sumb += b[i];
    for (int i = 1; i <= m; ++ i) {
        c[i] = read <LL> ();
        LL pos = ceil((double) c[i] / (double) b[i]);
        if (pos <= n) flow[pos].emplace_back(i);
    }
    auto sum = [] (int l, int r) { return s[r] - s[l - 1]; };
    sort(a + 1, a + n + 1); LL ans = s[n], s2 = 0, s1 = s[n];
    for (int i = 1; i <= n; ++ i) {
        s1 -= a[n - i + 1];
        for (int j: flow[i]) s2 += c[j], sumb -= b[j];
        ans = min(ans, s1 + s2 + 1ll * sumb * i);
    }
    printf("%lld\n", ans);
    return 0;
}
```

最后修改：2021 年 10 月 30 日