最少能量路径

版权信息：

CCF-CSP-J模拟

任务总览

题目描述

一个机器人需要从起点1移动到终点n。它的每一步消耗的能量与当前位置的高度差有关。给定一个长度为n的数组h，其中h[i]表示第i个位置的高度。机器人从起点1开始，初始能量为0。机器人只能向前移动（即从位置i移动到位置i+1），并且它在每一步的能量消耗为abs(h[i+1] - h[i])。机器人可以在任意位置进行能量补充，补充的能量只能为p的倍数，其中p为某个常数。求机器人从起点移动到终点所需的最少能量。

输入格式

• 第一行包含两个整数n和p，表示位置数量和能量补充的倍数。
• 第二行包含n个整数，表示每个位置的高度h[i]。

输出格式

• 输出一个整数，表示机器人到达终点所需的最少能量。

输入样例

5 10
10 20 15 25 10

输出样例

40

解题思路

1. ​问题分析​： 每一步，机器人移动到下一个位置时，消耗的能量是当前位置和下一个位置的高度差的绝对值：abs(h[i+1] - h[i])。 同时，机器人可以在任意位置进行能量补充，补充的能量必须是p的倍数。
2. ​步骤​：
   • 从起点（位置1）开始逐步计算每一步所需的能量。
   • 对于每一步，如果当前能量不足以到达下一个位置，机器人需要补充足够的能量。
   • 每次补充能量时，要确保补充量为p的倍数，即使机器人多补充一些，也可以确保能量满足下一个位置的需要。
3. ​策略​：
   • 初始化当前能量为0。
   • 对于每个位置i（从1到n-1），计算机器人从i到i+1的能量消耗abs(h[i+1] - h[i])。
   • 如果当前能量不足以移动到下一个位置，补充能量，使得补充量为p的倍数。
4. ​时间复杂度​：
   • 由于我们只需要从起点到终点遍历一次，并且每步的计算时间为常数，时间复杂度为O(n)，其中n为位置数量。

说明

• 代码首先定义了min_energy_path函数，该函数接受位置数量n、能量补充倍数p以及高度列表h作为输入。
• 在循环中，代码逐步计算从当前位置到下一位置的能量消耗，并判断是否需要补充能量。
• 补充的能量始终确保为p的倍数。
• 最后输出机器人到达终点所需的最少能量。

时间复杂度分析

• 每次移动所需的能量计算为O(1)，因此总时间复杂度为O(n)，其中n为位置数量。