问题陈述
给你一个长度为 $2N$ 的非负整数序列 $A = (A_1,\dots,A_{2N})$ 。
请定义长度为 $2N$ 的括号序列 $s$ 的得分如下：
- 对于 $s$ 的 $i$ 个字符为
)的每个位置 $i$ ，设置 $A_i$ 为 $0$ ，然后取 $A$ 中所有元素的和。
求长度为 $2N$ 的正确括号序列的最大可能得分。
给你 $T$ 个测试用例，请逐个求解。
什么是正确的括号序列？正确的括号序列是通过重复删除等于 ()的子串来还原为空字符串的字符串。
关键是对于任何一个合法的括号序列，前i个位置一定至少有(i+1) / 2 个 ( 括号
然后贪心即可
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n;
cin >> n;
priority_queue<int> q;
vector<int> a(2*n);
for (int i = 0; i < 2*n; i++) {
cin >> a[i];
}
int ans = 0;
for (int i = 0; i < n; i++) {
if (i == 0) {
q.push(a[i]);
} else {
q.push(a[i*2]);
q.push(a[i*2-1]);
}
ans += q.top();
q.pop();
}
cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}