Solution - Atcoder ARC125E Snack

观察到这种都是数量上限的限制，且求 \(\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;
}