A16660 | $Symmetrical Polygons$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

给定 $n$ 根木棍，第 $i$ 根木棍的长度为 $a_i$。你需要选择这些木棍的一个非空子集，并将它们作为一个多边形的边。每根被选中的木棍必须被完整地作为一个边使用，不能将两根或更多木棍端对端拼接以组成更长的边。 你的目标是用这些木棍组成立一个满足如下条件的多边形： - 对称（Symmetrical）：存在一条对称轴，使得沿这条轴折叠时多边形的两半完全重合。 - 严格凸（Strictly convex）：所有的内角都严格小于 $180^\circ$。 - 非退化（Non-degenerate）：没有两条相邻的边部分或完全重合，没有零长度的边，且没有 $180^\circ$ 的角。 在所有可以组成立如上所述多边形的方案中，求最大可能的周长（即所有边长之和）。如果无法组成合法的多边形，则输出 $0$。

每组测试包括多组测试数据。第一行包含一个整数 $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$。

输入 #1

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

输出 #1

C++ 编辑器

输入

输出