题解

题目分析

本题要求判断能否通过安排比赛使得所有机器人都被淘汰。关键在于是否存在一个“绝对冠军”机器人——即在力量和敏捷度两方面都严格大于所有其他机器人的机器人。如果存在这样的机器人，它无法被淘汰，答案就是 NIE；否则答案是 TAK。

算法思路

核心观察

将机器人按力量值 $s$ 排序后（题目中 $s$ 互不相同且范围为 $1$ 到 $n$，可以直接用数组下标表示），如果敏捷度 $z$ 也是严格递增的，那么力量最大的机器人（即 $s=n$ 的机器人）在两方面都最大，就是绝对冠军。

算法步骤

1. 数据存储：用数组 r[] 存储，r[s] = z 表示力量为 $s$ 的机器人的敏捷度为 $z$
2. 单调栈处理：维护一个单调递减栈，找出按力量排序后的“敏捷度递减序列”
3. 关键判断：
   • 如果栈大小为偶数，说明可以两两配对互相淘汰，输出 TAK
   • 如果栈大小为奇数，检查是否存在外部机器人能淘汰栈顶或栈底机器人

算法正确性

• 栈中元素构成一个“支配链”，栈顶力量最小但敏捷度相对较高，栈底力量最大
• 当栈大小为奇数时，只有栈中机器人可能成为绝对冠军
• 通过检查栈外机器人能否淘汰栈顶或栈底，确保没有绝对冠军

算法标签

• 单调栈 (Monotonic Stack)
• 支配对分析 (Dominant Pair Analysis)
• 贪心思想 (Greedy)

复杂度分析

• 时间复杂度：$O(n)$，每个元素入栈出栈一次
• 空间复杂度：$O(n)$，存储数组和栈

代码亮点

1. 利用力量和敏捷度互不相同的性质简化存储
2. 单调栈高效找出关键机器人
3. 奇偶性判断减少不必要的检查
4. 只检查栈顶栈底即可覆盖所有情况

该算法高效地解决了大规模数据下的机器人淘汰问题，核心在于通过单调栈识别潜在的绝对冠军候选人，并通过有限检查确认是否存在淘汰方案。