2019.3.31三角形三邊問題

最長周長三角形 O(nlogn)

  有n根棍子，棍子i的長度為ai。想要從中選出三根棍子組成周長盡可能長的三角形。請輸出最大的周長，若無法組成三角形輸出0.

思路

  很容易想到采用三重循環來枚舉所有三角形，複雜度為O(n3)O(n3)成立。這是應該将第n條邊排除在外。這樣最多排除n-2次，就能知道是否能組成三角形。

實作代碼

#include <stdio.h>
#include <algorithm>
using namespace std;

const int maxn =  + ;
int a[maxn];

int getMAXC(int a[], int n) {
    sort(a, a + n);
    for(int i = n - ; i >= ; i++) {
        if(a[i] < a[i - ] + a[i - ])
            return a[i] + a[i - ] + a[i - ];
        }
    return ;
}

int main() {
    int n;
    while(scanf("%d", &n) == ) {
        for(int i = ; i < n; i++) {
            scanf("%d", &a[i]);
        }
        printf("%d\n", getMAXC(a, n));
    }
    return ;
}

                
如有不當之處歡迎指出！