卡牌游戏：最大化军队能量值

问题描述 一副牌有 n 张卡牌，每张卡牌都有其威力。卡牌有两种类型： · 英雄卡，该卡的能量值始终等于 0； · 能量卡，这种卡的能量值总是正整数。您可以使用该套牌执行以下操作： · 从牌堆顶取出一张牌； · 如果这张卡是能量卡，你可以将其置于你的卡组顶部或丢弃； · 如果这张卡是英雄卡，则该英雄卡将获得你的卡组顶部的能量卡所拥有的能量值（如果卡组不为空），之后该英雄被添加到你的军队中，并且使用的能量卡被丢弃。你的任务是利用这些操作来组建一支拥有最大可能总能量值的军队。

输入格式 第一行一个整数 n，表示一副牌有的卡牌张数。第二行 n 个整数 s1,s2,…,sn 按照从牌堆顶到牌堆底的顺序描述这一副牌，如果 si 为 0，则表示这张卡是英雄卡，否则这张卡为能量卡。

输出格式 一行一个整数，表示组建的军队所拥有的最大可能的总能量值。

输入样例 1 5 3 3 3 0 0

输出样例 1 6

输入样例 2 6 0 3 3 0 0 3

输出样例 2 6

输入样例 3 7 1 2 5 0 4 3 0

输出样例 3 9

样例解释 对于第一个样例，你可以把第一张和第二张能量卡加入卡组，并且接下来两个英雄卡都会获得 3 的能量。如果你把全部的能量卡加入卡组，得到的答案也不会变化，其中一张能量卡将不会被使用到。对于第二个样例，牌堆顶的英雄卡没有办法获得能量，因为此时你没有能量卡，然后剩下的两个英雄卡可以通过第二张卡和第三张卡各自获得 3 的能量，总计能量为 6。对于样例 3，你可以将 1，2，3，5 号能量卡加入卡组，并跳过 6 号能量卡，4 号英雄卡将会获得 3 号能量卡的能量值为 5，7 号英雄卡将会获得 5 号能量卡的能量为 4，答案为 5+4=9。

数据范围及约定 对于 50% 的数据，1≤n≤5000 对于 100% 的数据，1≤n≤2×10^5，0≤si≤10^9

解题思路

这道题可以使用贪心算法来解决。

我们首先将所有能量卡按照从大到小的顺序排列。然后从牌堆顶开始遍历，如果遇到英雄卡，则将其添加到军队中，同时将能量卡从能量卡数组中删除。如果遇到能量卡，则将其添加到能量卡数组中。

最后，我们将能量卡数组中的能量值加起来即为所求的最大可能总能量值。

算法步骤

读入 n 和牌堆的序列。
定义一个数组 energy_cards 来存储能量卡，初始化为空。
遍历牌堆的序列，如果当前牌是英雄卡，则将其添加到军队中，同时将能量卡数组中的所有能量值加到当前英雄卡上；如果当前牌是能量卡，则将其添加到能量卡数组中。
计算能量卡数组中的能量值之和，输出结果。

算法复杂度

该算法时间复杂度为 O(nlogn)，空间复杂度为 O(n)。

源码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> pile(n);
    for (int i = 0; i < n; i++) {
        cin >> pile[i];
    }

    vector<int> energy_cards;
    long long total_energy = 0;

    for (int i = 0; i < n; i++) {
        if (pile[i] == 0) {
            if (!energy_cards.empty()) {
                int energy = energy_cards.back();
                energy_cards.pop_back();
                total_energy += energy;
            }
        } else {
            energy_cards.push_back(pile[i]);
            sort(energy_cards.begin(), energy_cards.end(), greater<int>());
        }
    }

    cout << total_energy << endl;

    return 0;
}