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

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

题目描述

一位代码勇者来到金苹果岛，岛上有两种苹果：提升代码能力的红苹果和使能力翻倍的金苹果。勇者初始代码能力为1，需要按指定顺序吃掉所有红苹果，但可以自由安排吃金苹果的时机。目标是最大化最终的代码能力。

输入格式

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

输出格式

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

解题思路

本题采用贪心算法。由于金苹果的效果是翻倍，为了最大化最终能力值，应该在代码能力非负时尽可能多吃金苹果。因此，我们可以先将所有红苹果按提升值从小到大排序，然后遍历红苹果：

1. 如果当前红苹果提升值为负且还有金苹果，则吃掉一个金苹果，使能力翻倍后再吃红苹果，以减少负面影响。2. 否则，直接吃掉当前红苹果。

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 = 0; i < n; i++) { if (a[i] < 0 && m > 0) { m--; } else { ans += a[i]; } } if (m > 0) { ans *= (1 << m); } cout << ans << endl; return 0;}

代码解析

1. 输入处理: 读取红苹果和金苹果的数量，以及每个红苹果的提升值。2. 排序: 将红苹果按提升值从小到大排序。3. 贪心策略: 遍历排序后的红苹果，优先在负提升值时使用金苹果。4. 计算最终能力值: 累加红苹果的提升值，并在最后乘以剩余金苹果的翻倍效果。

总结

这道题目的核心在于理解金苹果翻倍效果的价值，并利用贪心策略在合适的时间点使用，以最大化最终的代码能力。