你今天有 N 個長度不等的木棒,而你想知道這些木棒能組合出幾種「直角三角形」。
範例測資
範例輸入 | 範例輸出 |
---|---|
第一行有一數字 T ,代表有幾組測試資料 (1 <= T <= 50) 每組測試資料包含兩行 第一行有一數字 N ,代表有幾根木棒 (1 <= N <= 100) 第二行有 N 個數字 ai 以空白隔開,代表木棒的長度 (1 <= ai <= 100) | 對於每筆測試資料輸出一行,每行包含一個數字 x 代表可以組成幾種直角三角形。 |
3 3 3 4 5 6 3 3 4 4 5 5 3 3 4 6 | 1 8 0 |
解題思路
收資料的時候同一個數字只需收一次,但是要用 Map 紀錄這個數字出現的次數,並且存放到陣列的時候可以先將資料進行平方。
將陣列排序過後使用兩個 For迴圈 來取陣列中的任意兩數,代表 a^2 + b^2 = c^2 的 a 和 b。只需判斷 c 是否在Map中有超過一個數量就可以判斷這樣的組合是否為直角三角形。
因為同一個數字可能會超過一個,所以答案要 += MAP[a] * MAP[b] * MAP[c]。
範例程式碼-ZeroJudge B557: 直角三角形
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
for (int i = 0; i<T; i++)
{
vector<int>num;
map<int, int>MAP;
int N, ans = 0;
cin >> N;
for (int j = 0; j<N; j++)
{
int tmp;
cin >> tmp;
tmp = pow(tmp, 2);
if (MAP[tmp] == 0) num.push_back(tmp);
MAP[tmp]++;
}
sort(num.begin(), num.end());
for (int j = 0; j<num.size(); j++)
{
for (int k = j+1; k<num.size(); k++)
{
int c = num[j] + num[k];
if (MAP[c] > 0) ans += MAP[num[j]] * MAP[num[k]] * MAP[c];
}
}
cout << ans << "\n";
}
}
//ZeroJudge B557
//Dr. SeanXD