In "Harry Potter and the Goblet of Fire", after the Triwizard Tournament held at Hogwarts, not only Beauxbatons Academy of Magic and Durmstrang Institute, but also various magic schools from around the world began to send requests to Hogwarts for student exchanges. Headmaster Albus Dumbledore believed that allowing Hogwarts students to study at other magic schools would promote international magical cooperation. Therefore, Dumbledore decided to form a task force with the principals of other schools to organize this exchange student program.
Since it was the first time organizing such a program, Dumbledore did not want to open too many exchange spots. To keep it simple, he stipulated that for every student wishing to transfer from school A to school B, there must also be a student wishing to transfer from school B to school A. Only then would the task force approve their exchange, making the exchange student program a success. Including Hogwarts, students from all over eagerly applied.
Now, the task force has given you a task: to write a program to calculate the number of valid exchange student pairs that meet the requirements.
Sample Inputs/Outputs
| Sample Output(s) | Sample Output(s) |
|---|---|
| EOF inputs: for each test case, the first line contains a positive integer N (1 ≤ N ≤ 100), representing the number of students applying for an exchange. The next N lines each contain one student's application (each student can have only one application), which consists of two different positive integers A and B separated by a space. This indicates that the student wants to transfer from school A to school B. Here, A and B are guaranteed to be different numbers. | For each set of test data, please output the number of valid student exchange pairs. For example, if a student from school A wants to exchange with a student from school B, and a student from school B wants to exchange with a student from school A, the count of valid exchange cases increases by one pair (see output example). If there are no valid exchange cases, please output 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 |
Thought Process
使用 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]++。
Sample Code－ZeroJudge B563: Exchanging Students
#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