题解：CF2207B One Night At Freddy's

· · 题解

思路

如果对面一直增加当前危险等级最大的玩偶，那么当你重置它后，剩下的玩偶危险等级都很低，最终最大值反而很小。

所以对面会尽量让所有玩偶的危险等级均匀增长，每一秒增加当前危险等级最小的玩偶。这样无论你重置哪个玩偶，剩余的玩偶危险等级都较高，最终最大值才会更大。

显然，每次手电筒应该重置当前危险等级最大的玩偶，以最大程度降低最大值。

假设当前是第 i 次使用手电，那么包括这一次在内，你还有 n-i+1 次重置机会。每次重置可以消除一个当前最大值，因此最终的最大值只可能来自当前危险等级最大的 n-i+2 个玩偶。

所以每次使用手电筒前，我们只需要用一个multiset维护当前最大的 n-i+2 个危险等级的玩偶即可。

submission