观察到这种都是数量上限的限制,且求 \(\max\)。
所以可以考虑网络流建模,而流量就对应着给的糖果数。
令 \(S\) 为源点,\(T\) 为汇点,编号为 \(1\sim n\) 的点对应的糖果的种类,编号为 \(n + 1\sim n + m\) 的点对应的小孩。
连边 \((S, i, a_i)\),表示第 \(i\) 种糖果数不超过 \(a_i\) 个。
连边 \((i, n + j, b_j)\),表示第 \(j\) 个小孩吃单种糖果不超过 \(b_j\) 个。
连边 \((n + j, T, c_j)\),表示第 \(j\) 个小孩总共不能吃超过 \(c_i\) 个糖果。
但是在 \(n, m\le 2\times 10^5\) 的情况下,跑最大流明显有点废。
考虑一个套路,根据最大流最小割定理有最大流 \(=\) 最小割,所以转而去求这个图的最小割。
考虑这个图的最小割怎么求。
首先令 \(\operatorname{type}_i = S \operatorname{or} T\),代表 \(i\) 点是属于 \(S\) 集合还是 \(T\) 集合。
能发现对于 \(\operatorname{type}_i\) 的分配方式,对应的割的大小就为 \((\sum\limits_{i = 1}^n a_i[\operatorname{type}_i = T]) + (\sum\limits_{j = 1}^m b_j[\operatorname{type}_{n + j} = T]\times \sum\limits_{i = 1}^n [\operatorname{type}_i = S]) + (\sum\limits_{j = 1}^m c_j[\operatorname{type}_{m + j} = S])\)。
发现对于 \(i, j\) 之间的贡献对于 \(i\) 这一方其实只有 \(\sum\limits_{i = 1}^n [\operatorname{type}_i = S]\)。
这启发考虑枚举这个 \(c = \sum\limits_{i = 1}^n [\operatorname{type}_i = S]\) 来做。
- 对于 \(\sum\limits_{i = 1}^n a_i[\operatorname{type}_i = T]\)。
易知这就是让最大的 \(c\) 个 \(a_i\) 对应的 \(\operatorname{type}\) 为 \(S\)。 - 对于 \((\sum\limits_{j = 1}^m b_j[\operatorname{type}_{n + j} = T]\times c) + (\sum\limits_{j = 1}^m c_j[\operatorname{type}_{m + j} = S])\)。
相当于就是求 \(\sum\limits_{j = 1}^m \min\{b_j\times c, c_j\}\)。
这个可以知道 \(b_j\times c\le c_j\) 当且仅当 \(c\le \lfloor\frac{c_j}{b_j}\rfloor\),就可以 \(\mathcal{O}(1)\) 维护了。
时间复杂度 \(\mathcal{O}(n\log n)\),瓶颈在排序。
#include<bits/stdc++.h>
using ll = long long;
const int maxn = 2e5 + 10;
ll a[maxn], b[maxn], c[maxn];
std::vector<int> id[maxn];
int main() {
int n, m; scanf("%d%d", &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]);
for (int i = 1; i <= m; i++) {
ll ti = c[i] / b[i] + 1ll;
if (ti <= (ll)n) id[ti].push_back(i);
}
std::sort(a + 1, a + n + 1, [&](ll x, ll y) {return x > y;});
ll sum = 0, add = 0, ans;
for (int i = 1; i <= n; i++) sum += a[i];
for (int i = 1; i <= m; i++) add += b[i];
ans = sum;
for (int i = 1; i <= n; i++) {
sum -= a[i], sum += add;
for (int j : id[i]) sum -= b[j] * i, add -= b[j], sum += c[j];
ans = std::min(ans, sum);
}
printf("%lld\n", ans);
return 0;
}
标签:Atcoder,Snack,limits,int,sum,times,ARC125E,type,operatorname
From: https://www.cnblogs.com/rizynvu/p/18287938