[Extremely Easy] P12113 [NWRRC2024] If I Could Turn Back Time

xiezheyuan · 2025-04-24 15:43:44 · 题解

很怀疑出题人的精神状态 +1。注意到题目给出的山峰侵蚀操作满足下面两个性质：

• 操作是保序的（指无论进行多少次山峰侵蚀操作，若定义全序关系 \preceq 为 \leq，则两座山峰的高度的关系始终不变）。
• 操作是单调的（指无论进行多少次山峰侵蚀操作，原本高度高的山峰，被侵蚀的次数一定比高度低的山峰多）。

于是根据这两个性质，我们只需要将序列按照 h 为第一关键字，w 为第二关键字排序，依次检验一下是否满足操作次数单调即可。最后的答案就是所有山峰的操作次数最大值。时间复杂度 O(\sum n\log n)，QOJ Submission。