ZeroJudge B557: 直角三角形

你今天有 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
標籤

相關文章

發佈留言