C語言經典算法題：從數組中選三根棍子組成最大周長三角形

這是一道典型的組合優化問題：給定 n 根棍子，選擇 3 根能構成三角形且周長最大。本文提供完整思路分析、優化策略與可直接運行的 C 代碼實現。

問題建模

• 輸入：正整數 n (3 ≤ n ≤ 1000) 及 n 條邊長 a_i。
• 輸出：能構成三角形的三元組最大周長，無解輸出 0。
• 三角形不等式：任意兩邊之和 > 第三邊。排序後僅需檢查 a[i] + a[j] > a[k] (i < j < k)。

算法演進

暴力三重循環 O(n³) —— 適用於 n ≤ 200

int maxPerimeter = 0;
for (int i = 0; i < n; ++i)
    for (int j = i+1; j < n; ++j)
        for (int k = j+1; k < n; ++k)
            if (a[i] + a[j] > a[k] && a[j] + a[k] > a[i] && a[i] + a[k] > a[j])
                maxPerimeter = max(maxPerimeter, a[i]+a[j]+a[k]);

排序 + 雙指針 O(n² log n) —— 推薦方案

1. 將數組升序排序。
2. 固定最長邊 k (從 n-1 遞減至 2)。
3. 雙指針 i=0, j=k-1 尋找滿足 a[i] + a[j] > a[k] 的最大 a[i]+a[j]。
4. 若找到即為當前 k 下的最大周長，因數組有序，k 越大周長潛力越大，首次找到即全局最優，可直接返回。

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 1000

int cmp(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

int main(void) {
    int n;
    printf("輸入棍子數量 n: ");
    if (scanf("%d", &n) != 1 || n < 3 || n > MAX_N) return 1;
    
    int a[MAX_N];
    printf("輸入 %d 條邊長: ", n);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    
    qsort(a, n, sizeof(int), cmp);  // 升序
    
    int ans = 0;
    for (int k = n-1; k >= 2 && !ans; --k) {  // 找到即退出
        int i = 0, j = k-1;
        while (i < j) {
            if (a[i] + a[j] > a[k]) {
                ans = a[i] + a[j] + a[k];
                break;  // 當前 k 最大周長
            } else {
                ++i;    // 和太小，增大較小邊
            }
        }
    }
    
    printf("最大周長: %d\n", ans);
    return 0;
}

複雜度分析

測試用例

輸入:
5
2 3 4 5 10

排序後: 2 3 4 5 10
k=4(10): i=0,j=3 → 2+5=7 ≯ 10 → i=1 → 3+5=8 ≯ 10 → i=2 結束
k=3(5):  i=0,j=2 → 2+4=6 > 5 ✓ → ans=2+4+5=11

輸出: 最大周長: 11

擴展思考

• 若需輸出具體三邊長，記錄 i, j, k 即可。
• 若邊長為浮點數，比較時引入 eps 容差。
• 若 n 極大 (10⁵+)，可考慮桶排序 + 邊長頻率統計優化至 O(maxV)。

掌握「排序後固定最大邊 + 雙指針」模板，不僅能秒殺此題，更能舉一反三解決「三數之和」、「有效三角形個數」等經典變體。