[ARC125E] Snack 题解

不难发现一个较简单的网络流模型：

• 源点向所有糖果 \(i\) 连 \(a_i\) 的容量；
• 所有糖果向所有人 \(i\) 连 \(b_i\) 的容量；
• 所有人 \(i\) 向汇点连 \(c_i\) 的容量。

但第二步中建出的边数达到了惊人的 \(O(nm)\)，显然过不去。

考虑优化。从最大流角度优化较困难，由于最大流等价于最小割，我们可以从最小割的角度进行优化。

考虑先枚举源点到每个糖果的边是否断掉，设保留了 \(l\) 个糖果。那么每个人都有两种决策：把到 \(l\) 个糖果的边全部断掉，或是断掉到汇点的边，代价是 \(\min(lb_i,c_i)\)。

发现这个决策与具体选了哪些糖果无关，故我们可以先把不保留代价大的糖果保留，即按 \(a_i\) 降序排序，依次选糖果。观察第 \(i\) 个人的代价 \(\min(lb_i,c_i)\)，由于 \(l\) 是递增的，所以必定存在某个时刻 \(k_i\)，使得 \(k_ib_i>c_i\) 且 \((k_i-1)b_i\le c_i\)，即在 \(k_i\) 之前第 \(i\) 个人的决策是 \(lb_i\)，但到 \(k_i\) 之后第 \(i\) 个人的决策就变成了 \(c_i\)。把人按 \(k_i\) 升序排序，于是所有人决策总变化量是 \(O(n)\) 的，双指针即可。

#include <numeric>
#include <iostream>
#include <algorithm>

using namespace std;
using LL = long long;

const int kN = 2e5 + 1;

int n, m, b[kN], d[kN];
LL a[kN], c[kN], k[kN], ans;

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for (int i = 1; i <= m; ++i) {
    cin >> b[i];
  }
  for (int i = 1; i <= m; ++i) {
    cin >> c[i];
    k[i] = c[i] / b[i] + 1;
    d[i] = i;
  }
  sort(a + 1, a + n + 1, greater<LL>());
  sort(d + 1, d + m + 1, [](int i, int j) { return k[i] < k[j]; });
  LL s = accumulate(a + 1, a + n + 1, 0LL), vc = 0, bs = accumulate(b + 1, b + m + 1, 0LL);
  ans = s;
  for (int i = 1, j = 1; i <= n; ++i) {
    s -= a[i], vc += bs;
    for (; j <= m && k[d[j]] <= i; ++j) {
      vc -= 1LL * i * b[d[j]] - c[d[j]], bs -= b[d[j]];
    }
    ans = min(ans, s + vc);
  }
  cout << ans;
  return 0;
}