切換
舊版
前往
大廳
主題

ZeroJudge - a768: pD. 小蝦的煩惱 解題心得

Not In My Back Yard | 2019-06-06 22:49:04 | 巴幣 0 | 人氣 168

題目連結:


題目大意:
給定一正整數 N (N ≦ 3, 000),代表有 N 條邊。接著的一列有 N 個正整數(大小皆在 2 ^ 30 以內),代表這 N 條邊的長度。

求從這 N 條邊取三條,可以組出多少種相異的直角三角形?



範例輸入:
8
3 4 5 12 13 7 24 25


範例輸出:
3


解題思維:
因為題目是問「直角」三角形,而不是一般的三角形。因此,我們可以窮舉出兩條邊的取法,並得出以這兩條邊作為股的直角三角形之斜邊長應為何。

然後,得到了這個斜邊長之後可以先檢查其是否為整數(可以在計算前判斷,計算後也可以)。若為整數的話,再判斷在這 n 條邊有無長度相符的;若有的話,即得到了一組直角三角形。

為了方便判斷斜邊長有無在 n 條邊裡,我們可以先將其進行排序(由小到大排)。接著只要窮舉兩股,找出斜邊長。並計算出在其當中有出現過幾個合理的直角三角形即可。

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

創作回應

更多創作