題目連結:
給定一正整數 n ( n ≦ 100, 000 ),代表有 n 列輸入。每一列有 3 個數字(皆介於 1 ~ 2, 147, 483, 647),代表 3 跟木棍的長度。
判斷每一組木棍可不可以組成一個三角形,可以組成三角形的那些組之總數為 m 。然後,對於某一組的三角形 i ,其他組的三角形與其相似的總組數為 Xi 。
求 m 值,與其中最大的 Xi 。
3
1 1 1
2 2 2
1 2 3
2 1
首先,要能組成三角形的條件為:其中兩邊長之和大於第三邊之長。
而換句話說就是:兩較短邊長度之和大於最長邊之長度。
因此我們每輸入三個數字,可以先對其排序,看第一個數字 + 第二個數字是否 > 第三個數字。若非如此,就略過這組數字,不計到 m 值裡面;反之,判斷是否與之前的三角形相似(可以三邊長的比例去判斷)。有就把相似數 + 1 。
最後,跑一次陣列(儲存處理過後的輸入數字)判斷哪個相似數最大(Xi)。最後輸出 m 和Xi 即可。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。