題目敘述
每筆測資第一行有一個正整數T,接下來會有T筆資料,每筆資料第一行會有一個正整數N,第二行有N個正整數代表不同長度的木棒。要求輸出每一筆資料中可以生成幾組直角三角形。
範例輸入 #1
3
3
3 4 5
6
3 3 4 4 5 5
3
3 4 6
範例輸出 #1
1
8
0
解題思路
收資料的時候同一個數字只需收一次,但是要用Map紀錄這個數字出現的次數,並且存放到陣列的時候可以先將資料進行平方。將陣列排序過後使用兩個For迴圈來取陣列中的任意兩數,代表 a^2 + b^2 = c^2 的a和b。只需判斷c是否在Map中有超過一個數量就可以判斷這樣的組合是否為直角三角形。因為同一個數字可能會超過一個,所以答案要 += MAP[a] * MAP[b] * MAP[c]。
解題程式碼如下 (僅供參考):
#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";
}
}
留言
張貼留言