526互联

Codeforces Round 855 (Div. 3) C. Powering the Hero

发布时间 2023-10-21 21:06:15作者: zsxuan

有 \(n\) 张卡的卡堆，你可以自顶向下抽卡。装备卡显示数值为 \(a_i(a_i>0)\) ，英雄卡显示数值为 \(a_i = 0\) 。

如果是装备卡，你可以将卡抽出放在装备堆。如果是英雄卡，你可以将装备堆顶端的一张数值为 \(x\) 的装备卡装备给英雄，英雄数值 \(+ x\) 。无论是否装备，都加入英雄堆。

询问卡堆摸完后，英雄堆中所有英雄的数值最高为多少。

可以使用一个数据结构维护住数值当前最高的的装备卡。

每抽出一张英雄卡，取出当前最高的装备卡，在卡堆的位置为 \(i_k\) 。

于是可以得到 \(i_1, i_2, \cdots, i_k\) 。如果预先可以得到这组位置，就可以把对应的装备卡放入装备堆。

实际上我们只需要计算最终所有英雄的数值，所以不需要保存他们的位置，直接统计出装备数值即可。

具体算法为使用大根堆维护装备，当遇到英雄卡，若堆非空，堆顶的装备加入贡献。

view 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
void solve(){
	int n; std::cin >> n;
	std::priority_queue<int, std::vector<int>, std::less<int> > q;
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		int x; std::cin >> x;
		if (x) q.push(x);
		else if (!q.empty()) ans += q.top(), q.pop();
	}
	std::cout << ans << '\n';
}
int main() { 
	int _ = 1; std::cin >> _;
	while (_--) solve();
	return 0;
}