ZeroJudge B563: 魔法學校交換生問題

〈哈利波特－火盃的考驗》中，在霍格華茲所舉辦的三巫鬥法大賽結束之後，不只是波巴洞魔法女校、德姆蘭魔法軍校這雨所魔法學校，還有來自世界各地的魔法學校都陸續發函對霍格華茲提出交換學生的要求。校長阿不思•鄧不利多也認為如果本校學生也可以到其他魔法學校進行學習，這將能夠促進國際間的魔法交流。因此，阿不思•鄧不利多決定與各校校長組成一個專案小組來主辦這次的交換學生計畫，但由於是第一次主辦，鄧不利多不想開放太多的交換生的名額，為了簡單起見，規定每一個想從 A 學校換到 B 學校的學生必須也要有一個想從 B 學校交換到 A 學校的學生，這樣專案小組才能同意他們的交換，整個交換學生計畫才算是成功。包含霍格華茲在內，各地的學生都非常踴躍的申請，現在，專案小組交付你一個任務，就是寫一個程式來計算符合規定的交換學生案件配對數量。

範例測資

範例輸出範例輸出
EOF 輸入，每組測試資料的第一列含有 1 個正整數 N (1 ≤ N ≤ 100)，代表提出申請的學生個數。接下來的 N 列，每一列為一個學生的申請案 (一個學生只能有一個申請案），包含兩個不同的正整數 A 和 B，用空格字元做間隔，代表該學生想從 A 學校交換到 B 學校，這裡 A 跟 B 兩個數字不會一樣。對於每組測試資料，請輸出符合規定的交換學生案件配對數量。舉例來說，如果 A 學校的某一學生與 B 學校的某一學生互相交換，則符合規定的案件數量就增加了一對 (見輸出範例）。若沒有任何符合規定的案件數量，請輸出 0。
8
1 2
100 200
200 100
57 2
2 57
1 2
2 1
2 1
3
1 2
2 3
3 1		4
0

解題思路

使用 Pair<int, int> 的方式收 A 和 B，如果要配對成功的話就需要兩對一樣的數字但是不同排列方式。

宣告一個 Map<pair<int, int>, int>，如果 A > B，則判斷 Map[Pair] 中的資料是否 > 0，如果 > 0 的話，代表裡面有另外一邊可以配對的人，將答案 +1，將 A 和 B swap 之後將 Map[Pair]–。如果 A < B，則判斷 Map[Pair] 是否 < 0，如果 < 0 的話，代表裡面有另外一邊可以配對的人，將答案 +1，並將 Map[Pair]++。

範例程式碼－ZeroJudge B563: 魔法學校交換生問題

#include <iostream>
#include <map>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N;
    while (cin >> N)
    {
        map<pair<int, int>, int>MAP;
        int ans = 0;
        for (int i = 0; i<N; i++)
        {
            pair<int, int>school;
            cin >> school.first >> school.second;
            if (school.first > school.second)
            {
                swap(school.first, school.second);
                if (MAP[school] > 0) ans++;
                MAP[school]--;
            }
            else
            {
                if (MAP[school] < 0) ans++;
                MAP[school]++;
            }
        }
        cout << ans << "\n";
    }
}

//ZeroJudge B563
//Dr. SeanXD
標籤

相關文章

發佈留言