自动搬运

查看原文

来自洛谷，原作者为

	xiezheyuan 明明我已昼夜无间踏尽前路/梦想中的彼岸为何还未到/明明我已奋力无间/天天上路/我不死也为活更好/快要到终点才能知道/又再回到起点重头上路

搬运于2025-08-24 23:12:49，当前版本为作者最后更新于2025-04-24 15:43:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

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