#P13093. [FJCPC 2025] 卡牌游戏
[FJCPC 2025] 卡牌游戏
题目描述
小 A 和小 B 正在玩卡牌游戏。
有 张卡牌垒成一摞牌堆,自上而下的第 ()张牌上标注了数字 。发牌时,牌堆中的卡牌自上而下以 编号,编号为奇数的卡牌将分给一位玩家,编号为偶数的卡牌将分给另一位玩家。这意味着,小 A 将会获得编号同为奇数或同为偶数的 张卡牌。
对于玩家而言,所得到的卡牌上的数字之和越大,游戏局面对他越有利。因此小 A 想最大化最坏情况下他所得到的卡牌数字之和。为了达到这个目的,小 A 可以对当前牌堆执行恰好一次以下操作:
- 从当前牌堆中抽出一张卡牌,并插回牌堆中的任意位置。注意发牌时的编号可能会发生变化。
例如,初始时牌堆中卡牌标注的数字自上而下依次是 ,发牌时一位玩家将得到 ,另一位玩家将得到 。小 A 可以选择抽出第二张卡牌,并将其插回最后一张卡牌后面,此时牌堆为 ,发牌时一位玩家将得到 ,另一位玩家将得到 。
你需要求出小 A 在执行恰好一次操作后,最坏情况下所得到的卡牌数字之和的最大值。
输入格式
本题包含多组测试数据。
第一行,一个正整数 (),表示测试数据组数。
对于每组数据:
第一行,一个正整数 (),表示每位玩家将得到的卡牌数量。
第二行, 个正整数 (),表示当前牌堆中卡牌标注的数字。
对于每个测试点,保证 不超过 。
输出格式
对于每组数据,输出一行,一个整数,表示在执行恰好一次操作后,最坏情况下小 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
提示
第一组样例即是题目描述中所给出的例子。发牌时,一位玩家的卡牌数字之和为 ,另一位玩家的卡牌数字之和为 ,可以证明这即是所能取得的最大值。
第二组样例中,无论如何操作,发牌情况都将是一位玩家得到 ,而另一位玩家得到 。因此最坏情况下小 A 只能得到 ,即为答案。