自动搬运

查看原文

来自洛谷，原作者为

	yu10001909 代词使用她 || 快关注 @wzq_owo ！！！

搬运于2025-08-24 23:18:08，当前版本为作者最后更新于2025-08-19 10:28:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

原题传送门

题意简述

$z$ 组数据，每组数据读入 $n$ 条线段的长度，求拼成的多边形的最长 周长。

思路

多边形太难了，因此我们只考虑其中的一条边（理科牲狂喜）。

我们考虑一条边的两个顶点，那么这条边就是连接两个点的一条线段，多边形的其他边可以看成连接两个点的一条折线。

学过初中数学的都知道：两点之间线段最短（小知识：不是直线）。

所以我们假设选择的边是 $l_i$，那么满足以下等式：

$$l_i< l_1+l_2+\cdots+l_{i-1}+l_{i+1}+\cdots+l_n$$

于是我们只需要枚举 $i$，判断是否成立，再枚举减边，再枚举 $i$，……最后就 TLE 了。（虽然只有一个测试点）

于是我们明白我们需要优化了。

我们回顾刚刚的的式子：

$$l_i< l_1+l_2+\cdots+l_{i-1}+l_{i+1}+\cdots+l_n$$

可以看出，如果 $i$ 不是所有边里面最大的，那么式子一定是成立的，因为右边一定存在 $l_j$ 使得 $l_j>l_i$

于是我们可以预先对所有边从小到大排序，这样比较时就是：

$$l_n< l_1+l_2+\cdots+l_{n-1}$$

如果成立，当然万事大吉，直接输出就好了，如果不成立，我们就可以“扔掉”$l_n$，在继续判断就好了。这实际上是一个贪心的过程，现在我们来证明为什么是对的。 ::::success[证明] 对于上式不成立的情况，明显多边形一定是小于 $n$ 条边的，所以我们一定要删边。

如果删的是 $l_n$，自然不用说，但是如果删的是另一条边 $l_i$，那么上式左边不变，右边反而变小，就能得出需要继续删边，如此往复，最终我们会得到这些边无法构成多边形。

但是这显然是错误的，我们仅仅因为保留了一条边就删掉了其余的所有边，这无疑是荒谬的。因此我们必须删掉 $l_n$。 ::::

同样的，我们可以用前缀和来解决求和的问题。 ::::info[不会前缀和的看这里]

$$\begin{aligned} s_i&=l_1+l_2+\cdots+l_i\\ &=l_1+l_2+\cdots+l_{i-1}+l_i\\ &=s_{i-1}+l_i \end{aligned} $$

:::: 于是判断式就变成了：

$$l_n< s_{n-1}$$

同样的，该式如果成立，直接输出。不然就：

$$n \gets n-1$$

然后再继续判断。

终止条件

$n=2$ 时就无法构成多边形，此时直接输出就好。

其他

输出

输出如果是 $n$ 边形就直接输出 $s_n$ 就好了（想想为什么）。

排序

原题的边是 没有排序的，所以我们要先排序：

sort(l + 1, l + n + 1);

AC Code(c++)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 101000;
int z, n;
ll l[N], s[N];

int main() {
    scanf("%d", &z);
    while (z--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%lld", &l[i]);
        sort(l + 1, l + n + 1); // 排序
        s[0] = 0;
        for (int i = 1; i <= n; i++) s[i] = s[i - 1] + l[i]; // 前缀和
        int i;
        for (i = n; i >= 3; i--) // 这里我用 i 代替了 n，所以 i 要在循环体外面定义
            if (s[i - 1] > l[i]) break;
        if (i >= 3) printf("%lld\n", s[i]);
        else printf("0\n");
    }
    return 0;
}