正しい括弧列の定義にはさまざまな同値な言いかえが存在します。最も直感的な言い換えとして以下が挙げられます。

• \(1 \leq i \leq 2N\) において、\(S_1, \dots. \dots S_{i}\) のうち \(\frac{i}{2}\) 個以上が ( である。
• \(S_1, \dots, S_{2N}\) のうちちょうど \(N\) 個が ( である。

この条件の「\(\frac{i}{2}\) 個以上」の部分を主体にすることで、以下のように言い換えられます。

• \(1 \leq k \leq N\) において、\(S_1, \dots, S_{2k-1}\) のうち \(k\) 個以上が ( である。
• \(S_1, \dots, S_{2N}\) のうちちょうど \(N\) 個が ( である。

この条件を満たすような括弧列の構成として、以下の手続きが考えられます。

1. \(S_1\) を ( にする(これを便宜的に \(k=1\) のステップと考える)。
2. \(2 \leq k \leq N\) について昇順に、以下の操作を行う。
   • \({2k-2}\), \({2k-1}\) を候補の集合に追加する。
   • 候補の集合から要素 \(x\) を \(1\) つ選び、取り除く。その後、\(S_x\) を ( にする。
3. まだ ( にしていない \(N\) 個の文字を ) にする。

実際に、この手続きが作る任意の括弧列は正当な括弧列であり、任意の正当な括弧列はこの手続きで作ることが可能です。

この手続きが作りうる括弧列と正当な括弧列が等価であることの証明

この手続きで作った文字列 \(S\) において、任意の \(1 \leq t \leq N\) について

• \(1 \leq k \leq t\) を満たすそれぞれの \(k\) で \(S_1, \dots, S_{2t-1}\) のうちから \(1\) つを ( にしているので、\(S_1, \dots, S_{2t-1}\) のうち \(t\) 個以上が ( である。
• ( はちょうど \(N\) 個である。

よって \(S\) は正当な括弧列である。

逆に、正当な括弧列 \(S\) において、任意の \(1 \leq t \leq N\) について

• \(S_1\) は ( である。
• \(S_1, \dots, S_{2t-1}\) のうち、( は \(t\) 個以上ある。\(k = t\) の時点よりも前に選ばれて ( になったものは \(t-1\) 個しかないので、\(k=t\) の時点で選んでよい要素は少なくとも \(1\) つ存在する。
• ( はちょうど \(N\) 個である。

よって \(S\) を作る手続きが存在する。(証明完)

ここで、候補の集合から要素 \(x\) を選ぶ箇所において \(A_x\) の値が最大になるように選ぶことで、最終的な \(S\) のスコアを最大化することが、以下のように証明できます。

貪欲法が正当であることの証明

\(k = t\) の時点で、まだ選んでいない候補のうち \(A_x\) が最大であったが、これは選ばずに \(A_y ({} < A_x)\) を選んだときを考える。

• どの \(k > t\) でも \(A_x\) を選ばなかった場合: \(k = t\) の時点で \(A_y\) ではなく \(A_x\) を選び、他の \(k\) で同じ要素を選んだとしても、手続きは破綻しない。このとき最終的な \(S\) のスコアは増加している。
• ある \(k = t' > t\) で \(A_x\) を選んだ場合: \(k = t\) の時点で \(A_x\) を、\(k = t'\) の時点で \(A_y\) を選び、他の \(k\) で同じ要素を選んだとしても、手続きは破綻しない。このとき最終的な \(S\) のスコアは減少しない。

いずれにせよ、最終的な \(S\) のスコアがより小さくならないように、\(A_x\) を採る選び方に置き換えられる。

\(k < t\) での選び方は変化しないので、この置き換えは有限回で終了し、そのときの \(S\) は貪欲法による解と一致する。 (証明完)

実装は優先度付きキューを利用すれば簡潔です(C++ では標準で std::priority_queue が使えます)。

C++ での実装例を以下に示します。

#include <iostream>
#include <vector>
#include <queue>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
using std::vector;
using std::priority_queue;
using std::greater;


typedef long long ll;

ll solve (const ll n, const vector<ll> &a) {
	ll ans = 0;

	priority_queue<ll, vector<ll> > que;
	for (ll i = 0; i < n; i++) {
		if (i == 0) {
			que.push(a[i*2-0]);
		} else {
			que.push(a[i*2-1]);
			que.push(a[i*2-0]);
		}

		ll v = que.top();
		que.pop();

		ans += v;
	}

	return ans;
}

int main (void) {
	int T;
	cin >> T;
	while (T--) {
		ll n;
		cin >> n;
		vector<ll> a(n*2);
		for (ll i = 0; i < n*2; i++) {
			cin >> a[i];
		}

		cout << solve(n, a) << "\n";
	}

	return 0;
}