金苹果岛算法题解 - C++代码实现

题目描述

你来到了金苹果岛，岛上有两种苹果：提升代码能力的红苹果和使代码能力翻倍的金苹果。

• 初始代码能力为 1。- 红苹果按固定顺序吃，每个红苹果提升的代码能力可能不同，也可能为负数。- 金苹果可以随时吃，每个金苹果都会使当前代码能力翻倍。

给定红苹果的数量 n, 金苹果的数量 m，以及每个红苹果带来的代码能力提升值，求离开金苹果岛时所能获得的最大代码能力。

输入格式

• 第一行：两个正整数 n 和 m，分别表示红苹果和金苹果的数量。- 第二行：n 个整数，表示每个红苹果带来的代码能力提升值。

输出格式

• 一个整数，表示离开金苹果岛时所能获得的最大代码能力。

思路分析

为了最大化最终代码能力，应该在代码能力较高的时候吃金苹果。因此，我们可以将所有正的红苹果带来的代码能力提升值先加上，然后在适当的时机吃掉金苹果，最后再处理负的红苹果带来的影响。

C++代码实现cpp#include #include #include using namespace std;

int main() { int n, m; cin >> n >> m; vector apples(n); for (int i = 0; i < n; i++) { cin >> apples[i]; } sort(apples.begin(), apples.end()); long long maxAbility = 1; for (int i = 0; i < n; i++) { if (apples[i] > 0) { maxAbility += apples[i]; } else { break; } } for (int i = 0; i < m; i++) { maxAbility *= 2; } for (int i = 0; i < n; i++){ maxAbility += apples[i]; } cout << maxAbility << endl; return 0;}

代码解释

1. 读取输入的红苹果和金苹果数量，以及每个红苹果带来的代码能力提升值。2. 对红苹果带来的代码能力提升值进行排序，以便优先处理正的提升值。3. 遍历排序后的数组： - 如果当前红苹果带来的代码能力提升值为正，则将其加到当前代码能力上。 - 否则，跳出循环，因为负的提升值应该在最后处理。4. 将金苹果带来的翻倍效果应用到当前代码能力上。5. 最后处理剩下的负的红苹果带来的代码能力提升值。

示例

输入:

6 21 -2 3 1 -6 5

输出:

15

解释:

1. 排序后的红苹果提升值为: -6 -2 1 1 3 5.2. 先吃掉 1 1 3 5 这四个红苹果，代码能力变为 1 + 1 + 1 + 3 + 5 = 11。3. 吃掉两个金苹果，代码能力翻倍两次，变为 11 * 2 * 2 = 44。4. 最后吃掉 -6 -2 这两个红苹果，代码能力变为 44 - 6 - 2 = 36。

因此，最终答案为 36。