E - Takahashi Quest

2huk · 2023-12-16 21:44:37 · 题解

E - Takahashi Quest

Description

Takahashi 在进行一次冒险。

在第 i 个位置上发生一件事情，用 (t_i, x_i) 表示。

• 若 t_i = 1，则表示这里有一个 x_i 魔法的药水。Takahashi 可以选择捡起会不捡起；
• 若 t_i = 2，则表示这里有一个 x_i 魔法的怪兽，需要用一个 x_i 魔法的药水才能打败。

你需要求出，在 Takahashi 能打败所有怪兽的情况下，每个时刻手中的药水瓶数的最大值最小是多少。若不能打败所有怪兽输出 -1。

Solution

首先考虑判断无解。当遇到一个怪兽 x_i 时，如果前面剩余的 x_i 药水数量为 0，那么显然无法打败，输出 -1 结束即可。否则将 x_i 药水数量减一。

若有解，即能打败所有怪兽，那么我们考虑用哪一瓶药水打败第 i 个怪兽。

因为我们希望让每时每刻 Takahashi 手中的药水数少，那么肯定不能让他拿着一瓶药水很长时间。具体地，对于一个 x_i 的怪兽而言，我们应该使用前面最后一个（也就是离 i 最近的）x_j 魔法的药水，使得 x_i = x_j。这样就可以保证手中的药水数少了。

实现上，我们可以用 vector 存储每个还没被用过的药水出现在哪里。每次遇到一个怪兽 x_i，我们找到第 x_i 个 vector 中的最大值 v，表示在 v 的位置捡起药水。然后在 v \sim i - 1 这一段时间内内手中的药水数量加一，差分维护即可。

Code

https://atcoder.jp/contests/abc333/submissions/48569389。