题解：AT_abc407_e [ABC407E] Most Valuable Parentheses

贪心题，我们先假设是这样选数的，()()()()()...，那么答案就是奇数位的和，删除的是偶数位。

从前往后处理数列时，每遇到一个奇数位 $i$，就可以找一下在位置 $i$ 之前被删除的数中是否有比 $a_i$ 还大的数。

• 如果没有就将 $a_i$ 计入答案。

• 如果有，就记最大被删数字位置为 $j$，将 $a_j$ 记录答案，$a_i$ 删除，括号序列就会发生交换，$j$ 显然是右括号，$i$ 是左括号，交换不破坏括号匹配。

求最大显然使用优先队列。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t,n;
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>t;
	while(t--){
		cin>>n;
		int ans=0;
		priority_queue<int> q;//存被删的数字 
		for(int i=1,x;i<=n*2;i++){
			cin>>x;
			if(i%2){
				if(q.size()&&q.top()>x)ans+=q.top(),q.pop(),q.push(x);//删 a[i] 留 a[j] 
				else ans+=x;//计入答案
			}else q.push(x);//删除这个数
		}
		cout<<ans<<"\n";
	}
	return 0;
}