金苹果岛 - 代码能力最大化 - 贪心算法

题目描述

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

• 红苹果: 随处可见，每个红苹果提升的代码能力可能不同，也可能是负数。* 金苹果: 稀有美味，每个金苹果都能使你的代码能力翻倍。

你拥有初始代码能力 1。苹果仙子会赠予你 n 个红苹果和 m 个金苹果，你需要吃光所有苹果。你必须按照仙子规定的顺序吃红苹果，但可以自由安排吃金苹果的时机。

请问，如何安排才能使你离开金苹果岛时的代码能力最大？

输入格式

第一行包含两个正整数 n 和 m，分别表示红苹果和金苹果的数量。

第二行包含 n 个整数 a_i，表示每个红苹果带来的代码能力提升。

数据范围:

• 1 <= n <= 10^5* 0 <= m <= 10* -10 <= 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。

提示

• 贪心策略: 尽量在代码能力较高时吃金苹果，以最大化收益。* 排序: 将红苹果按照提升能力排序，优先吃提升能力大的。

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 max_ability = 1; // 使用 long long 避免溢出    for (int i = 0; i < n; i++) {        if (apples[i] >= 0) {            max_ability += apples[i]; // 提升能力为正，直接吃        } else {            if (m > 0) {                max_ability *= 2; // 提升能力为负，且还有金苹果，先吃金苹果                m--;            } else {                max_ability += apples[i]; // 没有金苹果了，只能吃红苹果            }        }    }

cout << max_ability << endl;    return 0;