C2. Powering the Hero (hard version)

原创于 2023-09-29 14:36:12 发布 · 粉丝可见 · 340 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/133417761

题目：

样例：

`cobol<br/>5<br/>5<br/>3 3 3 0 0<br/>6<br/>0 3 3 0 0 3<br/>7<br/>1 2 3 0 4 5 0<br/>7<br/>1 2 5 0 4 3 0<br/>5<br/>3 1 0 0 4<br/>`

6 6 8 9 4

思路：

贪心思维题，这道题要求的是一张一张的凑卡牌，凑到的是力量赋值卡就存储好，抽到 0 就是英雄卡，当我们存储中有力量赋值卡，就将该力量赋值给该英雄，并获得该英雄的战力，求最佳操作获得的最大战力总和是多少。

我们将每次抽到的力量赋值卡存储的时候，遇到英雄卡，就赋值给最大存储即可，而赋值卡值最小的放到后面，倘若遇到了英雄卡，也会将该最小力量赋值卡赋值给英雄的，倘若没遇到，相当于弃用掉。

所以我们用个优先队列存储并赋值即可。

代码详解如下：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>
#define endl '\n'
#define int long long
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#define All(x) (x).begin(),(x).end()
#pragma GCC optimize(3,"Ofast","inline")
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;
 
inline void solve()
{
	int n,ans = 0;
	cin >> n;
	
	// 存储力量赋值卡,优先赋值的最大战力卡
	priority_queue<int>q;
	
	// 开始抽卡
	while(n--)
	{
		int x;
		cin >> x;
		
		// 如果是力量赋值卡，存储好赋值卡
		// 如果是英雄，判断是否有赋值卡，有则获得该最佳战力
		if(x) q.push(x);
		else if(q.size()) ans += q.top(),q.pop();
	}
	// 输出最佳战力总和
	cout << ans << endl;
}
 
signed main()
{
//	freopen("a.txt", "r", stdin);
	___G;
	int _t = 1;
	cin >> _t;
	while (_t--)
	{
		solve();
	}
	return 0;
}