题解：AT_abc407_e [ABC407E] Most Valuable Parentheses

· · 题解

这跟括号序列有关系？

考虑右括号随便放，反正都是 0，然后左括号尽量选大的，接着因为右括号随便放所以它一定是能够成合法括号序列的，最后显然要使它是合法序列那个右括号不能超过 \frac{i}{2}，原因显然，不必多说。于是直接用优先队列贪就行了。

代码：

#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;
}