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

题目描述

你是一位代码勇者，来到了传说中的金苹果岛。岛上有两种苹果：

红苹果: 随处可见，食用后能提升你的代码能力，但提升效果不一，可能为正也可能为负。* 金苹果: 非常稀有且美味，食用后能使你的代码能力直接翻倍。

你的初始代码能力为 1。苹果仙子将为你提供 n 个红苹果和 m 个金苹果，你需要吃光所有苹果。食用红苹果的顺序由仙子规定，但你可以自由选择何时食用金苹果。

请问，如何安排食用顺序才能使你离开金苹果岛时拥有最高的代码能力？

输入格式

第一行包含两个正整数 n 和 m (n ≤ 10^5, m ≤ 10)，分别代表红苹果和金苹果的数量。

第二行包含 n 个整数 a_i (|a_i| ≤ 10)，表示按顺序食用每个红苹果后代码能力的变化值。

输出格式

输出一个整数，表示离开金苹果岛时可能获得的最高代码能力值。

样例 #1

样例输入 #1

6 21 -2 3 1 -6 5

样例输出 #1

样例 #2

样例输入 #2

8 35 -3 -8 2 4 -11 9 1

样例输出 #2

提示

样例1解释

最优策略是：

吃掉红苹果 1,-2,3,1，代码能力变为 4。2. 吃掉 2 颗金苹果，代码能力变为 16。3. 吃掉红苹果 -6,5，代码能力变为 15。

子任务

对于 10% 的数据，a_i ≥ 0。* 对于 30% 的数据，m = 0。* 对于 70% 的数据，m = 1。* 对于 100% 的数据，n ≤ 10^5, m ≤ 10, |a_i| ≤ 10。

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

int main() { int n, m; cin >> n >> m; vector a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } sort(a.begin(), a.end()); int ans = 0; for (int i = n - 1; i >= 0; i--) { if (a[i] < 0 && m > 0) { m--; } else { ans += a[i]; } } ans *= (1 << m); cout << ans << endl; return 0;}

题解

这道题可以使用贪心算法来解决。

贪心策略:

优先处理负收益的红苹果: 由于金苹果的效果是翻倍，因此我们希望在代码能力较低的时候尽量少吃金苹果，以减少负收益的影响。所以应该先将负收益的红苹果与金苹果抵消。2. 排序后计算: 将红苹果按照收益从小到大排序，优先处理收益小的苹果，最后再将所有金苹果的翻倍效果应用到最终结果上。

代码解释:

读取输入数据，并将红苹果的收益存储在数组 a 中。2. 对 a 进行排序。3. 从收益最小的红苹果开始遍历，如果当前红苹果收益为负数且还有金苹果剩余，则使用一个金苹果抵消其负收益；否则，将当前红苹果的收益累加到最终结果 ans 中。4. 最后将 ans 乘以 2 的 m 次方，即应用所有金苹果的翻倍效果。

时间复杂度: O(nlogn)，主要取决于排序的时间复杂度。

空间复杂度: O(n)，用于存储红苹果的收益。