题解：AT_utpc2011_7 プログラミングコンテストチャレンジブック

· · 题解

\Large{\text{Solution}}

感觉思路很妙，但是我想不到。

首先默认给的长度有序，比较显然的一个东西：如果只要一个三角形，那么我们肯定选连续的三个，最长的那个只需要比短的两个的和短就行。那么我们称最长边和这两条略短边组成的三角形为最长边所在的三角形。

考虑枚举一个三角形的最长边，那么这个时候，如果它和最大的最长边所在的三角形没有共边，就可以选这个三角形和最大的三角形，否则，只能尝试选最大的最长边和它前面的五条边，尝试拼凑。只需预处理然后枚举一遍即可。

\Large{\text{Code}} 
#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <int, pii> piii;
const double PI = acos (-1);
const double eps = 1e-10;
const int N = 1e5 + 10, M = 2e5 + 10;
//const int mod = 1e9 + 7;
//const int mod = 998244353;

int a[N];
int b[N], cnt;

signed main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int ans = 0;
    sort (a + 1, a + n + 1);
    for (int i = 3; i <= n; i++)
        if (a[i - 1] + a[i - 2] > a[i]) b[++cnt] = i;
    for (int i = 1; i < cnt; i++)
    {
        if (b[i] < b[cnt] - 2) ans = max (ans, a[b[i]] + a[b[i] - 1] + a[b[i] - 2] + a[b[cnt]] + a[b[cnt] - 1] + a[b[cnt] - 2]);
        else
        {
            int a1 = a[b[cnt] - 5], a2 = a[b[cnt] - 4], a3 = a[b[cnt] - 3], a4 = a[b[cnt] - 2], a5 = a[b[cnt] - 1], a6 = a[b[cnt]];
            int tot = a1 + a2 + a3 + a4 + a5 + a6;
            if (a1 + a2 > a3 && a4 + a5 > a6) ans = tot; //这里不需要全部判断，可以想想为什么
            // if (a1 + a2 > a4 && a3 + a5 > a6) ans = tot;
            // if (a1 + a2 > a5 && a3 + a4 > a6) ans = tot;
            // if (a1 + a2 > a6 && a3 + a4 > a5) ans = tot;
            if (a1 + a3 > a4 && a2 + a5 > a6) ans = tot;
            // if (a1 + a3 > a5 && a2 + a4 > a6) ans = tot;
            // if (a1 + a3 > a6 && a2 + a4 > a5) ans = tot;
            if (a1 + a4 > a5 && a2 + a3 > a6) ans = tot;
            // if (a1 + a4 + a6 && a2 + a3 > a5) ans = tot;
            if (a1 + a5 > a6 && a2 + a3 > a4) ans = tot;
        }
    }
    cout << ans << "\n";
    return 0;
}