题解：AT_abc407_e [ABC407E] Most Valuable Parentheses

~~这跟括号序列有关系？~~

考虑右括号随便放，反正都是

0

，然后左括号尽量选大的，接着因为右括号随便放所以它一定是能够成合法括号序列的，最后显然要使它是合法序列那个右括号不能超过

\frac{i}{2}

，原因显然，不必多说。于是直接用优先队列贪就行了。

代码：

CPP

#include<bits/stdc++.h>
using namespace std;
const int N = 4e5+5;
int a[N];
signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int _;
	cin >> _;
	while(_--)
	{
		int n;
		cin >> n;
		n<<=1;
		for(int i = 1;i<=n;++i)
		{
			cin >> a[i];
		}
		priority_queue<int>q;
		long long ans = 0;
		for(int i = 1;i<=n;++i)
		{
			q.push(a[i]);
			if(q.size()>(i>>1))
			{
				ans+=q.top();
				q.pop();
			}
		}
		cout << ans << '\n';
	}
	return 0;
}

题解：AT_abc407_e [ABC407E] Most Valuable Parentheses

文章操作

相关推荐

评论

题解：AT_abc407_e [ABC407E] Most Valuable Parentheses