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

题目描述

你来到了金苹果岛，岛上有两种苹果：提升代码能力的红苹果和使代码能力翻倍的金苹果。

你的初始代码能力为 1。每个红苹果提升的代码能力可能不同，也可能是负数。每个金苹果都能使你的代码能力翻倍。

岛上的苹果仙子用 n 个红苹果和 m 个金苹果招待你，你需要吃光所有苹果。你必须按照仙子规定的顺序吃红苹果，但可以自由安排吃金苹果的时间（可以在吃任意一个红苹果之前或之后吃若干个金苹果）。

求你在离开金苹果岛的时候，代码能力的最大值。

输入格式

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

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

输出格式

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

样例

输入

6 21 -2 3 1 -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()); int ans = 0; for (int i = 0; i < n; i++) { if (apples[i] < 0 && m > 0) { m--; continue; } ans += apples[i]; } ans *= (1 << m); cout << ans << endl; return 0;}

解释

代码首先读取输入数据，并将红苹果的代码能力提升存储在 apples 向量中。

然后，代码对 apples 向量进行排序，以便优先处理提升较小的红苹果。

接下来，代码遍历排序后的 apples 向量。对于每个红苹果：

• 如果当前红苹果的代码能力提升为负数，并且还有剩余的金苹果，则跳过当前红苹果，并减少一个金苹果数量。这是因为吃掉负数提升的红苹果会降低代码能力，而金苹果可以将代码能力翻倍，因此应该将金苹果留到后面吃。- 否则，将当前红苹果的代码能力提升累加到 ans 变量中。

最后，将 ans 乘以 2 的 m 次方，即可得到最终的代码能力最大值。

复杂度分析

• 时间复杂度：O(n log n)，主要来自对红苹果的排序操作。- 空间复杂度：O(n)，用于存储红苹果的代码能力提升。