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
Use Pair to store A and B. For a successful match, you need two pairs with the same numbers but in different orders.
Declare a Map<pair, int>. If A > B, check if Map[Pair] has data greater than 0. If it does, it means there is a matching pair available, so increment the answer by 1, swap A and B, and decrement Map[Pair]. If A < B, check if Map[Pair] is less than 0. If it is, it means there is a matching pair available, so increment the answer by 1, and increment 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