#### 前言
这道题目的解法很多种，这里提供一种看似错误时间复杂度的正确做法以及证明，容我大放狂词，这是本题最优秀的算法，时间复杂度大概是O(n)。
#### 解法
首先把数据给出的 n 条边进行从小到大排序。
相信最大值大家都会，也就是判断第一个满足条件的 a[i] < a[i - 1] + a[i + 2] 的 a[i] + a[i - 1] + a[i - 2]
最小值暗藏玄机。
这是我寻找满足条件的最小周长三角形的做法
```cpp
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[i - 2] + s[i - 1] > s[i]$ 则必定存在小于等于$s[i - 2]$ 以及 $s[i - 1] $的$s[j] + s[k] > s[i]$
那么假设我们枚举到的最大边有解，我们就需要寻找一个最小边以及一个次小边使得s[j] + s[k] + s[i]最小，暴力枚举即可。
为什么直接不用二分也能过，而且只跑了**10ms**?
考虑什么情况下此算法复杂度被卡满。
首先考虑第一重循环，我们遇到的第一个有答案的i肯定不超过 100 次。然后时间复杂度就是O(50 + 100 * 100)的，因为第二三重循环都只循环到i。
理性分析，要使得本算法最劣，实际上就是尽量使得第一个有答案的i尽可能大。
首先, $s[i - 1] + s[i - 2] <= s[i]$，要满足这个关系尽可能的久，不难发现我们实际上需要构造一个斐波那契数列。
为什么呢?
证明：
假设最小的边为 x , 第二个为y , 第三个就得大于等于 x + y ,那么第三个就会是大于等于 x + y + y 的，第四个就会是大于等于 x + y + y + y + x 的。
易得，我们第一个为x = 1的时候最劣，也就是构造斐波那契数列，然而a[i]是小于等于1e9的，那么最多枚举i不超过50次，因此得到最小值需要的时间几乎可以忽略!
因此这是最优算法。
```cpp
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 返回在所有合法的三角形的组成中，最大的三角形的周长减去最小的三角形的周长的值
* @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;
}
};
```
全部评论
(4) 回帖