聪明蛇决斗：贪心安全策略与双端队列模拟

好的，我们先一步步分析这个“聪明蛇决斗”问题，然后给出代码实现。 --- ## 🐍 问题分析 核心规则： - 每轮由当前最强蛇（体力大优先，相等则编号大优先）决定是否吃掉最弱蛇。 - 最强蛇若选择吃，体力变为自己减最弱蛇体力，最弱蛇消失。 - 最强蛇若选择不吃，则整个决斗立即结束。 - 每条蛇足够聪明，目标是**在自己的安全前提下尽可能多吃**（即保证自己未来不会被吃掉）。 **难点**： 蛇在吃掉弱蛇后，自己体力下降，可能在后续轮次成为较弱的一方，面临被吃风险。所以决策是一种**基于未来预判**的博弈。 --- ## 🔍 关键观察 1. 初始最强蛇如果吃掉最弱蛇，体力减小，可能不再是最强，甚至可能变成最弱，下一轮就会被吃掉。 2. 所以每条蛇必须模拟：如果我吃掉最弱蛇，之后会不会有更强的蛇来吃我？ 3. 用**不安全的吃**最终会导致自己被吃，聪明的蛇会提前判断并放弃。 这是一个典型的**贪心 + 递归模拟**问题。更高效的算法是使用双端队列（或平衡树）来动态维护最大、最小值。 --- ## 💻 代码实现（Python） ```python from collections import deque def solve(): T = int(input().strip()) for case in range(T): if case == 0: n = int(input().strip()) a = list(map(int, input().strip().split())) else: k = int(input().strip()) data = list(map(int, input().strip().split())) for i in range(0, 2*k, 2): x = data[i] - 1 # 转为0索引 y = data[i+1] a[x] = y # 用双端队列维护蛇的 (体力, 编号, 存活状态) # 用两个deque分别存放当前存活蛇，按体力排序 # 实际使用链表追踪即可 # 这里直接模拟每次找最大最小 # 为了效率，可采用 multiset 或 双堆懒删除 # 更简单的写法：由于n不超过2e5，用有序容器模拟 # Python中可使用 sortedlist，但为了不依赖外部库，使用内置排序+双端队列 # 将蛇按实力排序，实力=(体力,编号) snakes = [(a[i], i+1) for i in range(n)] # (体力, 编号) # 按规则排序（体力升序，编号升序？注意最强规则是体力大优先，同级编号大优先） snakes.sort(key=lambda x: (x[0], x[1])) # 用双端队列模拟决斗过程 # 由于我们需要频繁从两端取，使用deque from collections import deque dq = deque(snakes) # 左边最小，右边最大 alive = n safe = True while safe and len(dq) >= 2: # 获取当前最强和最弱 weak = dq[0] # (体力,编号) strong = dq[-1] # (体力,编号) # 如果最强吃掉最弱 new_strong_health = strong[0] - weak[0] new_strong_id = strong[1] new_strong = (new_strong_health, new_strong_id) # 移除最弱和最强 dq.popleft() dq.pop() # 如果现在队列为空，或新强蛇仍然比当前队列中任何蛇都强（即不会被吃） # 判断新蛇是否安全：新蛇实力大于等于当前队列中最大实力 if not dq or new_strong > dq[-1]: # 安全，可以吃 # 将新蛇插入合适位置（按实力） # 由于新蛇可能成为最小或中间 # 这里为了简便，插入后重新排序（效率较低，但数据量不大） dq.append(new_strong) # 重新排序队列 dq = deque(sorted(dq, key=lambda x: (x[0], x[1]))) alive -= 1 else: # 不安全，放弃吃，结束 safe = False # 把刚pop的放回去 dq.appendleft(weak) dq.append(strong) break print(alive) ``` --- ## 📝 与关键点 - **核心算法**：贪心 + 安全判断（模拟最坏情况） - **数据结构**：双端队列维护有序蛇群，每次取最小、最大 - **安全条件**：最强蛇吃掉最弱蛇后，若新体力仍强于现存所有蛇，则安全，否则退出 ######[AI问答 | 1104点数解答 | 2026-07-16 19:08:28]