A16660. Symmetrical Polygons
编程题
普及-
知识点
题目描述
给定 $n$ 根木棍，第 $i$ 根木棍的长度为 $a_i$。你需要选择这些木棍的一个非空子集，并将它们作为一个多边形的边。每根被选中的木棍必须被完整地作为一个边使用，不能将两根或更多木棍端对端拼接以组成更长的边。
你的目标是用这些木棍组成立一个满足如下条件的多边形：
- 对称（Symmetrical）：存在一条对称轴，使得沿这条轴折叠时多边形的两半完全重合。
- 严格凸（Strictly convex）：所有的内角都严格小于 $180^\circ$。
- 非退化（Non-degenerate）：没有两条相邻的边部分或完全重合，没有零长度的边，且没有 $180^\circ$ 的角。
在所有可以组成立如上所述多边形的方案中，求最大可能的周长（即所有边长之和）。如果无法组成合法的多边形，则输出 $0$。
你的目标是用这些木棍组成立一个满足如下条件的多边形：
- 对称（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$。
每组测试数据的第一行包含一个整数 $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
17 0 0 23 0
说明/提示
在第一个测试用例中，你可以使用所有三根木棍构成一个等腰三角形。它沿着垂直虚线对称（见左图）。周长等于三条边之和：$5 + 5 + 7 = 17$。
在第二个测试用例中，用所有三根木棍围成的三角形不是对称的（见右图）。可以证明，无法用任意非空子集的木棍构成对称、非退化的凸多边形。
在第三个测试用例中，无法构成非退化多边形。若用三条边全部参与，长度为 $5$ 的两条边与长度为 $10$ 的边重合，形成了一条零面积的直线。
在第四个测试用例中，我们可以用三根长度为 $3$ 的木棍、两根长度为 $5$ 的木棍和一根长度为 $4$ 的木棍（见左图）构成一个对称的凸多边形。长度为 $1$ 的最后一根木棍不能被包括，否则得到的多边形将不再对称（见右图）。
在第五个测试用例中，不允许将长度为 $2$ 的木棍和 $3$ 的木棍连接形成长度为 $5$ 的木棍（这样就变成第一个测试用例的情形）。可以证明，无法用任意非空子集的木棍构成对称、非退化的凸多边形。
在第二个测试用例中，用所有三根木棍围成的三角形不是对称的（见右图）。可以证明，无法用任意非空子集的木棍构成对称、非退化的凸多边形。
在第三个测试用例中，无法构成非退化多边形。若用三条边全部参与，长度为 $5$ 的两条边与长度为 $10$ 的边重合，形成了一条零面积的直线。
在第四个测试用例中，我们可以用三根长度为 $3$ 的木棍、两根长度为 $5$ 的木棍和一根长度为 $4$ 的木棍（见左图）构成一个对称的凸多边形。长度为 $1$ 的最后一根木棍不能被包括，否则得到的多边形将不再对称（见右图）。
在第五个测试用例中，不允许将长度为 $2$ 的木棍和 $3$ 的木棍连接形成长度为 $5$ 的木棍（这样就变成第一个测试用例的情形）。可以证明，无法用任意非空子集的木棍构成对称、非退化的凸多边形。