C语言/数据结构前缀和题解：机器人能量冒险——求满足全程能量≥1的最小初始能量

问题描述

小明的机器人R2-D2正在进行一场能量冒险。在冒险地图上，有若干个能量站，每个能量站提供一定数值的能量（可能为负值）。机器人需要从起点出发，按顺序访问每个能量站并收集能量，但在任意时刻机器人的总能量都不能低于1，否则就会停止运行。

现在给定一个能量数组energies，表示按访问顺序排列的各能量站提供的能量值。请帮助小明计算，机器人要成功完成整个冒险（访问所有能量站且中途能量始终≥1），初始至少需要多少能量？

要求：

测试样例

样例1：

输入：energies = [1, -2, 3, -4, 5] 输出：3 解释：初始能量为2时：2+1=3(≥1) → 3-2=1(≥1) → 1+3=4(≥1) → 4-4=0(＜1，失败)。初始能量为3时：3+1=4 → 4-2=2 → 2+3=5 → 5-4=1 → 1+5=6，成功完成。

样例2：

输入：energies = [-1, -2, 5, -3] 输出：4 解释：初始能量4时：4-1=3 → 3-2=1 → 1+5=6 → 6-3=3，全程≥1。

样例3：

输入：energies = [3, -5, 2, -1] 输出：3 解释：初始能量2时：2+3=5 → 5-5=0(＜1，失败)。初始能量3时：3+3=6 → 6-5=1 → 1+2=3 → 3-1=2，成功。

约束条件

• 1 ≤ energies.length ≤ 1000
• -1000 ≤ energies[i] ≤ 1000
• 保证存在解（总能找到满足条件的初始能量）
• 初始能量必须为整数

程序代码

#include <stdio.h>

int minInitialEnergy(int* energies, int energiesSize) {

    int sum = 0;

    int minSum = 0;  // 记录最小的前缀和

    for (int i = 0; i < energiesSize; i++) {

        sum += energies[i];

        if (sum < minSum) {

            minSum = sum;

        }

    }

    // 最小初始能量 = 1 – minSum

    // 但如果 minSum >= 0，初始能量为1即可

    int result = 1 – minSum;

    if (result < 1) result = 1;

    return result;

}

int main() {

    int energies1[] = {1, -2, 3, -4, 5};

    int energies2[] = {-1, -2, 5, -3};

    int energies3[] = {3, -5, 2, -1};

    printf("%d\\n", minInitialEnergy(energies1, 5));  // 3

    printf("%d\\n", minInitialEnergy(energies2, 4));  // 4

    printf("%d\\n", minInitialEnergy(energies3, 4));  // 3

    return 0;

}

#include <stdio.h>

int minInitialEnergy(int* energies, int energiesSize) {
int sum = 0;
int minSum = 0; // 记录最小的前缀和

for (int i = 0; i < energiesSize; i++) {
sum += energies[i];
if (sum < minSum) {
minSum = sum;
}
}

// 最小初始能量 = 1 – minSum
// 但如果 minSum >= 0，初始能量为1即可
int result = 1 – minSum;
if (result < 1) result = 1;

return result;
}

int main() {
int energies1[] = {1, -2, 3, -4, 5};
int energies2[] = {-1, -2, 5, -3};
int energies3[] = {3, -5, 2, -1};

printf("%d\\n", minInitialEnergy(energies1, 5)); // 3
printf("%d\\n", minInitialEnergy(energies2, 4)); // 4
printf("%d\\n", minInitialEnergy(energies3, 4)); // 3

return 0;
}

运行结果