金苹果岛上的代码挑战

题目描述

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

• 红苹果: 随处可见，食用后能提升你的代码能力，但提升效果可能不同，甚至会降低能力。* 金苹果: 稀有珍贵，食用后能使你的代码能力直接翻倍！

你的初始代码能力为 1。苹果仙子将为你提供 n 个红苹果和 m 个金苹果，你必须全部吃完。食用红苹果的顺序由仙子规定，但你可以自由选择在任何时间吃金苹果。

你的目标是：制定最佳的策略，最大化你离开金苹果岛时的代码能力！

输入格式

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

第二行包含 n 个整数 a_i (-10 ≤ a_i ≤ 10)，表示每个红苹果对代码能力的影响。

输出格式

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

示例

输入 #16 21 -2 3 1 -6 5

输出 #115

解释:

• 首先吃掉影响力为 1, -2, 3, 1 的红苹果，代码能力变为 4。* 然后吃掉两个金苹果，代码能力翻倍两次，变为 16。* 最后吃掉剩下的两个红苹果 (-6, 5)，最终代码能力为 15。

提示

• 贪心策略： 尝试在代码能力较低时吃掉金苹果，以最大化翻倍效果。* 负面影响： 红苹果可能降低你的代码能力，需要谨慎选择食用时机。* 子任务: 题目包含多个难度级别，逐步挑战自我，最终解决完整问题！

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 ans = 1; // 初始代码能力为1 for (int i = 0; i < n; i++) { if (apples[i] < 0) { ans += apples[i]; // 吃红苹果，代码能力提升 } else { ans *= 2; // 吃金苹果，代码能力翻倍 m--; // 金苹果数量减少 } if (m == 0) { break; // 金苹果吃完了，退出循环 } } cout << ans << endl; return 0;}

时间复杂度: O(n log n), 主要来自排序操作。

挑战: 你能想出其他解题思路吗？尝试使用动态规划等方法解决这个问题！