技术编程题求解：Hide and Seek（猫鼠躲猫猫问题）

问题分析 #

核心矛盾在于：老鼠需要在汤姆到达其初始位置前，完成足够步数逃到鼠洞；汤姆会直接向鼠洞移动，途中抓捕所有未及时逃离的老鼠。双方均采取最优策略：老鼠优先让最容易逃脱的个体行动，汤姆则以最快速度向鼠洞移动以最大化抓捕数量。

关键观察 #

1. 每只老鼠逃到鼠洞需要的步数为 s_i = N - x_i（x_i 是老鼠与汤姆的初始距离，N 是汤姆到鼠洞的距离）。
2. 汤姆到达老鼠 i 的初始位置需要 x_i 步，在此之前，老鼠共有 x_i 次行动机会（每次汤姆行动前，有一次老鼠行动的机会）。
3. 要让老鼠 i 获救，需保证前面所有获救老鼠的总行动步数之和不超过 x_i（否则汤姆到达该位置时，老鼠还未完成逃离）。

最优策略（贪心算法） #

1. 排序：将老鼠按与汤姆的距离 x_i 从大到小排序（离鼠洞越近的老鼠，x_i 越大，需要的逃离步数 s_i 越少，且汤姆到达其位置的时间越晚，可用行动机会越多）。
2. 累加验证：依次累加每只老鼠的逃离步数，若累加和超过当前老鼠的 x_i，则后续老鼠均无法获救，停止计算；否则计数加一。

代码实现 #

n, k = map(int, input().split())
x = list(map(int, input().split()))
x.sort(reverse=True)

sum_s = 0
count = 0

for num in x:
    s = n - num
    sum_s += s
    if sum_s > num:
        break
    count += 1

print(count)

样例验证 #

样例输入1：

2 4
1 1 1 1

• 排序后 x 仍为 [1,1,1,1]，每只老鼠的逃离步数 s_i=1。
• 累加第一个 s_i=1，1<=1，计数为1。
• 累加第二个 s_i=2，2>1，停止计算。最终输出1，符合样例结果。

内容的提问来源于stack exchange，提问作者rishav krishna