ETH官方钱包

切換
舊版
前往
大廳
主題

ZeroJudge - b352: 相似 解題心得

Not In My Back Yard | 2018-12-24 22:51:33 | 巴幣 0 | 人氣 132

題目連結:


題目大意:
給定一正整數 n ( n ≦ 100, 000 ),代表有 n 列輸入。每一列有 3 個數字(皆介於 1 ~ 2, 147, 483, 647),代表 3 跟木棍的長度。

判斷每一組木棍可不可以組成一個三角形,可以組成三角形的那些組之總數為 m 。然後,對於某一組的三角形 i ,其他組的三角形與其相似的總組數為 Xi 。

求 m 值,與其中最大的 X


範例輸入:
3
1 1 1
2 2 2
1 2 3



範例輸出:
2 1



解題思維:
首先,要能組成三角形的條件為:其中兩邊長之和大於第三邊之長。

而換句話說就是:兩較短邊長度之和大於最長邊之長度。

因此我們每輸入三個數字,可以先對其排序,看第一個數字 + 第二個數字是否 > 第三個數字。若非如此,就略過這組數字,不計到 m 值裡面;反之,判斷是否與之前的三角形相似(可以三邊長的比例去判斷)。有就把相似數 + 1 。

最後,跑一次陣列(儲存處理過後的輸入數字)判斷哪個相似數最大(X)。最後輸出 m 和X 即可。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

追蹤 創作集

作者相關創作

更多創作