c268: 簡單的三角形

2019-08-23

內容

電仁今天以國手的身份來到了某間學校擔任特別講師。由於他覺得下面的學員們實在是太弱了，他決定先從簡單的三角形開始教起。”三角形是由三條線段順次首尾相連，或不共線的三點兩兩連接，所組成的一個閉合的平面圖形，是最基本的多邊形…”電仁發現即使使用了那麼淺白的文字說明，下面的學員們似乎還是不懂他在講甚麼。於是他想到了個好辦法，讓學生們實際拿東西拼成三角形就可以加深大家的印象了!電仁晚上回到自己的宿舍，決定從宿舍拿一些長條形的磁鐵隔天帶去學校給學生們拿來拼三角形(他在宿舍門前按門鈴時不小心釋放身體裡的電流把門鈴燒壞了，這又是另一個故事了…)

電仁拿了 n 根長磁鐵條前往學校，在路上時他想到一件可怕的事：會不會這些長磁鐵條中沒有任何 3 根磁鐵條能拼成一個三角形啊!畢竟構成三角形需要滿足一個基本性質，也就是任兩邊的和要大於第三邊。如果他只拿了長度為 1,5,10,20 的四根磁鐵，不管拿哪 3 條出來都無法構成三角形!由於電仁可能帶著許多磁鐵條，沒辦法迅速心算驗證，請你幫忙判斷電仁帶的 n 根磁鐵條中，有沒有任何 3 根可以構成一個三角形。

輸入

第一行有一個整數 T 代表有 T 筆資料。接下來兩行是第一筆資料：第一行有一個整數 n 代表電仁帶了幾根磁鐵條；第二行有 n 個整數 ai 代表每一根磁鐵條的長度。再接下來兩行是第二筆測試資料，依此類推。

(T≦5,1≦n≦5*10⁷,1≦ai≦10⁹)

3
3
3 4 5
4
1 5 10 20
3
10 10 10

輸出

輸出共 T 行。對於每一筆資料輸出一行代表這筆資料的 n 根磁鐵條中，有沒有任何 3 根可以構成一個三角形。有的話輸出 YES，否則輸出 NO。

YES
NO
YES

解題思路

先把當有 n 個磁鐵條時，能夠"不"組合成三角形的的最小長度組合列出來

n = 3 {1, 1, 2}
n = 4 {1, 1, 2, 3}
n = 5 {1, 1, 2, 3, 5}
n = 6 {1, 1, 2, 3, 5, 8}
…

發現最小組合剛好是費式數列，而當 n 為 45 時數列末項為 1134903170 (費式數列第 45 項)

n = 45 {1, 1, 2, 3, ….701408733, 1134903170}

由於輸入說明中磁鐵條最長為 10⁹，但當有 45 條磁鐵條時，必須有長度大於 1134903170 的磁鐵條才可能"不"形成三角形，所以當 n >= 45 時必定會形成三角形。

既然已經知道在這題 n >= 45 時必定會形成三角形，那麼當 n >= 45 時就不必對該筆測資進行判斷，輸出 YES 後把該筆測資的磁鐵條長度資料全部捨棄掉讀取下筆測資即可。

完整程式碼

AC (38ms, 1.1MB)

#include <stdio.h>
#include <stdlib.h>
#define MAX 1048576

int t, n, list[50];
char s[MAX + 10], isTriangle;

int cmp(const int* lhs, const int* rhs)
{
    return *lhs - *rhs;
}

int main()
{
    while (scanf(" %d", &t) == 1)
    {
        while (t--)
        {
            scanf(" %d", &n);
            if (n > 44)
            {
                getchar();
                do
                {
                    s[MAX - 2] = -1;
                } while (fgets(s, MAX, stdin)[MAX - 2] != EOF);
                puts("YES");
            }
            else
            {
                isTriangle = 0;
                for (int i = 0; i < n; i++)
                    scanf(" %d", &list[i]);
                qsort(list, n, sizeof(int), cmp);
                for (int i = 2; i < n; i++)
                {
                    if (list[i - 2] + list[i - 1] > list[i])
                    {
                        isTriangle = 1;
                        break;
                    }
                }
                puts(isTriangle ? "YES" : "NO");
            }
        }
    }
    return 0;
}