CF2055E 题解

Albert_Wei · 2024-12-30 20:20:22 · 题解

\textup{\textbf{Part 1}}

考虑 b_i = \infty 的情况。我们发现，除了第一个清空的草垛，其他草垛中的草捆都可以放在比它早清空的草垛里，从而只需移动一次，而第一个草垛中的草捆无论如何都得放在比它后清空的草垛里，必须移动两次，所以答案为 \sum \limits_{i = 1} ^ n a_i + \min \limits_{i = 1} ^ n a_i。

\textup{\textbf{Part 2}}

考虑草垛清空顺序确定的情况（不妨设为从 1 到 n 依次清空），我们发现相比 b_i = \infty 的情况，差别是每一个草垛都有可能必须把草捆放在比它晚清空的草垛中。具体来说，是第 i 个草垛清空时，有 c_i = \max(0, \sum \limits_{j = 1} ^ i a_j - \sum\limits_{j = 1} ^ {i - 1} b_j) 个草垛必须放在比它晚清空的草垛中，所以答案至少为 \sum \limits_{i = 1} ^ n a_i + \max \limits_{i = 1} ^ n c_i，且必须保证 c_n = 0 （否则多出来的草捆就没地方放了）。又因为我们可以贪心地尽量把这一次清空中的草捆往已经清空的草垛中的空位丢，剩下的放到最晚清空的草垛里，这样可以保证所有草捆只被移动不超过两次，而且被扔到第 n 堆的草捆（即移动两次的草捆）不超过 \max \limits_{i = 1} ^ n c_i 个，所以答案必能取到 \sum \limits_{i = 1} ^ n a_i + \max \limits_{i = 1} ^ n c_i。

\textup{\textbf{Part 3}}

考虑去掉 c_n = 0 限制的情况。由于 n \le 5 \times 10 ^ 5，考虑使用调整法寻找贪心策略。首先，由于 \sum \limits_{j = 1} ^ i a_j - \sum\limits_{j = 1} ^ {i - 1} b_j = \sum\limits_{j = 1} ^ {i - 1} (a_j - b_j) + a_i，我们将 a_i - b_i \le 0 的草垛先清空显然不劣。其次，交换两个草垛 y, x 需要保证 \max(a_x, a_x - b_x + a_y) \le \max(a_y, a_y - b_y + a_x)。

• 对于 a_i - b_i \le 0 的部分，有 a_x - b_x + a_y \le a_y，所以只需保证 a_x \le a_y，按照 a 从小到大排序即可。
• 对于 a_i - b_i > 0 的部分，有 a_x < a_y - b_y + a_x，所以只需保证 a_x - b_x + a_y \le a_y - b_y + a_x，即 b_x \ge b_y，按照 b 从大到小排序即可。

  \textup{\textbf{Part 4}}

  考虑 c_n = 0 的限制，我们发现它要求 \sum \limits_{i = 1} ^ n (a_j - b_j) + b_n \le 0，即 b_n \le \sum \limits_{i = 1} ^ n (b_j - a_j)，可以预处理出有哪些草垛满足。于是我们只需要考虑去掉一个草垛后对 \sum\limits_{j = 1} ^ {i - 1} (a_j - b_j) + a_i 的影响。这只是对该草垛所在位置之后的值做一个后缀减，所以维护前、后缀最大值即可。总复杂度 \mathcal{O}(n \log n)，瓶颈在排序。

核心代码：

n = read(), pos.clear();
sum = tot = 0, pmx[0] = smx[n + 1] = -1e18;
for (int i = 1; i <= n; i ++) {
  t[i].a = read(), t[i].b = read();
  t[i].dlt = t[i].a - t[i].b, sum -= t[i].dlt, tot += t[i].a;
}
sort(t + 1, t + n + 1, [&](Thing x, Thing y) {
  if (x.dlt <= 0 && y.dlt > 0) return true;
  if (x.dlt > 0 && y.dlt <= 0) return false;
  if (x.dlt <= 0 && y.dlt <= 0) return x.a < y.a;
  return x.b > y.b;
});
for (int i = 1; i <= n; i ++)
  if (t[i].b <= sum) pos.push_back(i);
if (!pos.size()) return puts("-1"), void();
for (int i = 1; i <= n; i ++) {
  val[i] = val[i - 1] + t[i].a - t[i - 1].b;
  pmx[i] = max(pmx[i - 1], val[i]);
}
for (int i = n; i >= 1; i --) smx[i] = max(smx[i + 1], val[i]);
LL ans = 1e18;
for (int i : pos) Fmin(ans, max(pmx[i - 1], smx[i + 1] - t[i].a + t[i].b));
cout << max(0ll, ans) + tot << '\n';