牛客巅峰赛-牛牛与三角形 题解

前言

这道题目的解法很多种，这里提供一种看似错误时间复杂度的正确做法以及证明，容我大放狂词，这是本题最优秀的算法，时间复杂度大概是O(nlog(n))瓶颈在于排序。

解法

首先把数据给出的 n 条边进行从小到大排序。

相信最大值大家都会，也就是判断第一个满足条件的 a[i] < a[i - 1] + a[i + 2] 的 a[i] + a[i - 1] + a[i - 2]

最小值暗藏玄机。

这是我寻找满足条件的最小周长三角形的做法

        for(int i = 3 ; i <= n && flag; i ++)
        {
            if(s[i - 2] + s[i - 1] <= s[i])continue;
            for(int j = 1 ; j < i - 1 && flag; j ++)
            {
                for(int k = j + 1 ; k <= i - 1 && flag; k ++)
                    if(s[j] + s[k] > s[i])Min = s[j] + s[k] + s[i],flag = 0;//其实这里可以换成二分
            }
        }

看似是 O(n ^ 3) 的？

实际上是O(常数) 的。

为什么呢？

因为实际上我只需要找到第一个满足条件的三角形即可，找到第一个满足条件的就break。

枚举最大边即可。

则必定存在小于等于 以及 的

那么假设我们枚举到的最大边有解，我们就需要寻找一个最小边以及一个次小边使得s[j] + s[k] + s[i]最小，暴力枚举即可。

为什么直接不用二分也能过，而且只跑了10ms?

考虑什么情况下此算法复杂度被卡满。

首先考虑第一重循环，我们遇到的第一个有答案的i肯定不超过 100 次。然后时间复杂度就是O(50 + 100 * 100)的，因为第二三重循环都只循环到i。

理性分析，要使得本算法最劣，实际上就是尽量使得第一个有答案的i尽可能大。

首先, ，要满足这个关系尽可能的久，不难发现我们实际上需要构造一个斐波那契数列。

为什么呢?

证明：
假设最小的边为 x , 第二个为y , 第三个就得大于等于 x + y ,那么第三个就会是大于等于 x + y + y 的，第四个就会是大于等于 x + y + y + y + x 的。

易得，我们第一个为x = 1的时候最劣，也就是构造斐波那契数列，然而a[i]是小于等于1e9的，那么最多枚举i不超过50次，因此得到最小值需要的时间几乎可以忽略!

因此这是最优算法。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回在所有合法的三角形的组成中，最大的三角形的周长减去最小的三角形的周长的值
     * @param n int整型 代表题目中的n
     * @param a int整型vector 代表n个数的大小
     * @return int整型
     */
    int solve(int n, vector<int>& a) {
        int s[1000005];
        for(int i = 0 ; i < n ; i ++)
            s[i + 1] = a[i];
        sort(s + 1 , s + 1 + n);
        int Min = 0x3f,Ans = 0,Max = -1;
        for(int i = n ; i >= 3 ; i --)
        {
            int op;
            if(s[i - 1] + s[i - 2] <= s[i])continue;
            op = s[i - 1] + s[i - 2] + s[i];
            Max = max(Max,op);
        }
        int flag = 1;
        for(int i = 3 ; i <= n && flag; i ++)
        {
            if(s[i - 2] + s[i - 1] <= s[i])continue;
            for(int j = 1 ; j < i - 1 && flag; j ++)
            {
                for(int k = j + 1 ; k <= i - 1 && flag; k ++)
                    if(s[j] + s[k] > s[i])Min = s[j] + s[k] + s[i],flag = 0;
            }
        }
        Ans = Max - Min;
        return Ans;
    }
};