当前位置：首页 > article >正文

题目解析与Python实现：D. Lizards and Basements 2

article 2024/12/27 10:11:54

引言

在本文中，我们将详细解析一个有趣的编程题目“D. Lizards and Basements 2”，并使用Python来实现其解决方案。本题来自一个竞技编程比赛，既考察算法的实现能力，也对逻辑分析能力提出了挑战。

题目描述

Polycarp喜欢玩电脑角色扮演游戏《蜥蜴和地下室》。游戏中的最后几关，他需要与一排弓箭手战斗。他唯一的攻击手段是投掷火球。如果Polycarp将火球投掷到第 i 个弓箭手：

第 i 个弓箭手的生命值会减少 a 点。
相邻弓箭手（第 i-1 个和第 i+1 个）的生命值会减少 b 点。
两端的极端弓箭手（编号为1和n）不会受到火球的相邻伤害。

当某个弓箭手的生命值小于0时，他会被击杀。

目标是通过投掷火球，使得所有弓箭手的生命值均小于0。需要找到：

最小的火球投掷次数。
每次投掷火球的目标弓箭手编号（可以多次投掷到同一目标）。

输入格式

第一行输入包含三个整数 n, a, 和 b：

n (3 ≤ n ≤ 10)：表示弓箭手的数量。
a (1 ≤ a ≤ 10)：表示投掷火球对目标的直接伤害值。
b (1 ≤ b < a ≤ 10)：表示对相邻弓箭手的伤害值。

第二行输入一个长度为 n 的整数序列：

h1, h2, ..., hn (1 ≤ hi ≤ 15)：分别表示每个弓箭手的初始生命值。

输出格式

第一行输出最小的火球投掷次数 t。
第二行输出长度为 t 的整数序列，表示每次投掷火球的目标弓箭手编号（1-indexed）。

如果有多种解决方案，可以输出任意一种。

示例

输入示例 1

3 2 2
2 2 2

输出示例 1

3
2 2 2

解释：

第一次投掷火球到弓箭手2，弓箭手2的生命值减少2，相邻的弓箭手1和弓箭手3分别减少2。
重复两次该操作后，所有弓箭手的生命值都小于0。

输入示例 2

4 3 1
1 1 1 1

输出示例 2

4
2 3 2 3

解释：

按照题目规则，需要4次投掷才能击杀所有弓箭手。

解题思路

分析

约束条件：
- 弓箭手数量 n 的范围较小（最大为10），可以使用暴力解法。
- 每次投掷火球会对目标和相邻弓箭手造成伤害。
- 需要通过模拟过程来判断弓箭手是否被击杀。
解决方式：
- 按照题目要求，从第2个到第 n-1 个弓箭手（1-indexed）选择目标进行火球投掷。
- 每次投掷，记录目标弓箭手编号，并更新弓箭手的生命值。
- 重复上述过程，直到所有弓箭手生命值均小于0。
优化目标：
- 使用最少的火球投掷次数。
- 输出任何符合要求的解决方案。

Python实现

以下是完整的Python代码实现：

def minimum_fireballs(n, a, b, health_points):
    shots = []
    # 将输入的生命值列表复制为可修改列表
    health = health_points[:]

    for i in range(1, n - 1):  # 只考虑编号2到n-1（1-indexed）的弓箭手
        while health[i] > 0:  # 如果当前弓箭手还未被击杀
            # 向第i个弓箭手投掷火球（1-indexed）
            shots.append(i + 1)
            # 当前弓箭手的生命值减少a
            health[i] -= a
            # 左侧相邻弓箭手的生命值减少b
            if i - 1 >= 0:
                health[i - 1] -= b
            # 右侧相邻弓箭手的生命值减少b
            if i + 1 < n:
                health[i + 1] -= b

    # 确保所有弓箭手都被击杀
    assert all(h <= 0 for h in health), "还有弓箭手未被击杀！"

    # 输出结果
    print(len(shots))  # 最小火球投掷次数
    print(" ".join(map(str, shots)))  # 每次投掷的弓箭手编号


# 输入数据
n, a, b = map(int, input().split())
health_points = list(map(int, input().split()))

# 调用函数求解
minimum_fireballs(n, a, b, health_points)

代码详解

输入与初始化：
- 读取弓箭手数量 n，火球伤害值 a 和 b，以及弓箭手的生命值列表。
- 初始化一个列表 shots 用于记录每次投掷火球的目标弓箭手编号。
模拟火球投掷：
- 遍历编号为2到n-1的弓箭手（1-indexed）。
- 如果当前弓箭手的生命值 > 0，则向其投掷火球，并更新其生命值以及相邻弓箭手的生命值。
确保弓箭手全被击杀：
- 在循环结束后，使用 assert 语句确保所有弓箭手的生命值均小于等于0。
输出结果：
- 输出投掷次数 t。
- 输出每次投掷的弓箭手编号列表。