金苹果岛与最大代码能力：算法挑战

题目描述

一位代码勇者踏上了神秘的金苹果岛，岛上生长着两种神奇的苹果：

• 红苹果: 随处可见，食用后代码能力会得到一定提升（提升值可能为负）。* 金苹果: 稀有珍贵，食用后代码能力直接翻倍。

勇者初始代码能力为 1。苹果仙子为勇者准备了 n 个红苹果和 m 个金苹果，勇者必须吃光所有苹果。规则如下：

• 红苹果必须按照仙子规定的顺序吃。* 金苹果可以自由安排食用顺序，可以在任意红苹果之前或之后吃任意数量的金苹果。

勇者的目标是最大化离开金苹果岛时的代码能力。

输入格式

• 第一行：两个正整数 n (n≤10^5) 和 m (m≤10)，分别表示红苹果和金苹果的数量。* 第二行：n 个整数 a_i (|a_i|≤10)，表示每个红苹果对代码能力的提升值。

输出格式

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

样例

输入 #1

6 21 -2 3 1 -6 5

输出 #1

15

解释

勇者可以采取以下策略：

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());

long long ans = 1; // 初始代码能力为 1    for (int i = 0; i < n; i++) {        // 优先处理负提升的红苹果，并使用金苹果翻倍        if (a[i] < 0 && m > 0) {            ans *= 2;            m--;        }        ans += a[i];     }

// 剩余的金苹果全部使用    while (m--) {        ans *= 2;    }

cout << ans << endl;    return 0;}

算法解析

代码中采用了贪心策略，核心思想是在遇到负提升的红苹果时，优先使用金苹果进行翻倍，以最大化后续正提升红苹果的效果。

1. 排序: 将红苹果的提升值排序，方便后续处理。2. 贪心策略: 遍历排序后的红苹果，如果遇到负提升且还有金苹果剩余，则先使用金苹果翻倍当前代码能力，再处理红苹果的影响。3. 处理剩余金苹果: 最后将剩余的金苹果全部用于翻倍代码能力。

总结

本题结合了贪心算法和排序的思想，通过对问题的深入分析，找到最优策略，高效地解决了最大化代码能力的问题。