← 返回题目列表

Codeforces · 2153/C

C. 对称多边形

中文机器翻译题面 查看原题

你有 $$$n$$$ 根棍子,其中第 $$$i$$$ 根棍子的长度为 $$$a_i$$$。您想要选择这些棒的非空子集并将它们用作多边形的边。每个选定的棒必须完全用作多边形的单边。它是 不 允许将两根或多根棍子首尾相连并平行连接以形成更长的边。

您的目标是形成一个对称、严格凸且非退化的多边形:

  • 对称:存在一条对称线,使得当多边形沿这条线折叠时,两半完全重合。
  • 严格凸:其所有内角严格小于 $$$180^\circ$$$。
  • 非退化:没有两个连续的边至少部分重合,没有边的长度为零,并且没有角度等于 $$$180^\circ$$$。

在您可以用棍子形成的所有此类多边形中,找到最大可能的周长$$$^{\text{*}}$$$。如果不存在有效的多边形,则输出$$$0$$$。

$$$^{\text{*}}$$$多边形的周长等于其边长之和。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3\le n\le 2\cdot 10^5$$$) — 木棍的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i\le 10^9$$$) - 木棍的长度。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数,表示可以从棍子的非空子集形成的非退化、对称和严格凸多边形的最大可能周长。如果不可能,则输出$$$0$$$。

示例

输入
复制

5
3
5 5 7
3
4 5 7
3
5 5 10
7
4 3 5 1 5 3 3
4
2 3 5 7

输出
复制

17
0
0
23
0

注意

在第一个测试用例中,您可以使用所有三根棍子形成一个等腰三角形。它沿垂直虚线对称(见左图)。周长等于其边长之和:$$$5 + 5 + 7 = 17$$$。

在第二个测试用例中,所有三根棍子形成的三角形不对称(见右图)。可以证明,任何非空的棒子集都不能形成对称的、非退化的凸多边形。

在第三个测试用例中,不可能形成非退化多边形。如果使用所有三个边,则长度为 $$$5$$$ 的两条边与长度为 $$$10$$$ 的边重合,仅生成一条面积为零的直线。

在第四个测试用例中,我们可以使用三根长度为 $$$3$$$ 的棍子、两根长度为 $$$5$$$ 的棍子和一根长度为 $$$4$$$ 的棍子形成对称凸多边形(见左图)。长度为 $$$1$$$ 的最后一根棒不能包含在内,因为生成的多边形将不再对称(见右图)。

在第五个测试用例中,不允许将长度为 $$$2$$$ 和 $$$3$$$ 的棍子连接起来形成长度为 $$$5$$$ 的棍子(这将产生第一个测试用例)。可以证明,任何非空的棒子集都不能形成对称的、非退化的凸多边形。