Sol
首先暴力最大流肯定很容易搞出来,跑 $10^4$ 级别应该差不多?
考虑模拟最大流,因为最大流可能很大,因此把最大流换成最小割,来考虑割会有什么样的效果。
第二列点就代表零食,第三列就是小朋友。
现在考虑割,割从源点出发到第二列点的边,对最小割是没有影响的。因为第二列到第三列仍然没有发生改变,贡献给答案的只有 $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
#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;
}