小明爱吃糖

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小明有 nn 个糖果,编号从 11 到 nn,其中第 ii 颗糖果的价值是 aia_i,小梦总是对这些糖果虎视眈眈。

这天小梦提出要吃掉其中的恰好 22 颗糖果,他希望小明将糖果分成恰好两堆,接着他从每一堆糖果中都挑一个编号最大的糖果吃掉。

小明希望自己被小梦吃掉的 22 颗糖果价值之和尽可能小,请你帮他用合适的方式将糖果分堆,以求出这个最小的价值吧。

输入格式

本题含有多组测试数据。
第一行一个正整数 T (1≤T≤1000)T\ (1 \leq T \leq 1000),表示测试数据的组数。

接下来对于每组测试数据,输入包含两行。

第一行一个正整数 n (2≤n≤200000)n\ (2 \leq n \leq 200000),表示小明的糖果总数。
第二行 nn 个整数 ai (1≤ai≤100)a_i\ (1 \leq a_i \leq 100),表示每颗糖果的价值。

(保证所有测试数据中,nn 的总和不超过 200000200000。)

输出格式

对于每组测试数据,输出一行一个整数,表示小梦吃掉两颗糖果的最小价值之和。

样例

2
5
2 3 1 4 5
4
1 1 1 1
6
2

提示

对于第一组测试数据,小明最优的一种可能的分配方式是:
编号为:{1,3}\{1, 3\} 的糖果分一堆,编号为 {2,4,5}\{2, 4, 5\} 的糖果另一堆。
小梦会从每一堆里跳出编号最大的糖果,即:33 号和 55 号,价值之和为 66,最小。
(可以证明不存在比 66 更优的答案。)

2025级SYUCT-ACM新生第六次训练

未参加
状态
已结束
规则
XCPC
题目
21
开始于
2025-11-28 19:00
结束于
2025-12-15 11:00
持续时间
400 小时
主持人
参赛人数
106