#P13093. [FJCPC 2025] 卡牌游戏

[FJCPC 2025] 卡牌游戏

题目描述

小 A 和小 B 正在玩卡牌游戏。

2n2n 张卡牌垒成一摞牌堆,自上而下的第 ii1i2n1\leq i\leq 2n)张牌上标注了数字 aia_i。发牌时,牌堆中的卡牌自上而下以 1,2,,2n1, 2, \dots, 2n 编号,编号为奇数的卡牌将分给一位玩家,编号为偶数的卡牌将分给另一位玩家。这意味着,小 A 将会获得编号同为奇数或同为偶数的 nn 张卡牌。

对于玩家而言,所得到的卡牌上的数字之和越大,游戏局面对他越有利。因此小 A 想最大化最坏情况下他所得到的卡牌数字之和。为了达到这个目的,小 A 可以对当前牌堆执行恰好一次以下操作:

  • 从当前牌堆中抽出一张卡牌,并插回牌堆中的任意位置。注意发牌时的编号可能会发生变化。

例如,初始时牌堆中卡牌标注的数字自上而下依次是 1,2,3,41, 2, 3, 4,发牌时一位玩家将得到 1,31, 3,另一位玩家将得到 2,42, 4。小 A 可以选择抽出第二张卡牌,并将其插回最后一张卡牌后面,此时牌堆为 1,3,4,21, 3, 4, 2,发牌时一位玩家将得到 1,41, 4,另一位玩家将得到 3,23, 2

你需要求出小 A 在执行恰好一次操作后,最坏情况下所得到的卡牌数字之和的最大值。

输入格式

本题包含多组测试数据。

第一行,一个正整数 tt1t1041\leq t\leq 10^4),表示测试数据组数。

对于每组数据:

第一行,一个正整数 nn1n1051\leq n\leq 10^5),表示每位玩家将得到的卡牌数量。

第二行,2n2n 个正整数 a1,a2,,a2na_1, a_2, \dots, a_{2n}1ai1091\leq a_i\leq 10^9),表示当前牌堆中卡牌标注的数字。

对于每个测试点,保证 n\sum n 不超过 10510^5

输出格式

对于每组数据,输出一行,一个整数,表示在执行恰好一次操作后,最坏情况下小 A 所得到的卡牌数字之和的最大值。

4
2
1 3 2 4
1
1000000000 1
3
1 1 2 3 5 8
4
1 2 4 8 16 32 64 128
5
1
9
106

提示

第一组样例即是题目描述中所给出的例子。发牌时,一位玩家的卡牌数字之和为 1+4=51 + 4 = 5,另一位玩家的卡牌数字之和为 3+2=53 + 2 = 5,可以证明这即是所能取得的最大值。

第二组样例中,无论如何操作,发牌情况都将是一位玩家得到 11,而另一位玩家得到 10910^9。因此最坏情况下小 A 只能得到 11,即为答案。