Wenwen's alma mater is celebrating its centennial anniversary, and the alumni association is holding the "Outstanding Alumni Voting Event". After collecting all the alumni voting ballots, they've handed them over to you to assist in tallying the votes.
Sample Inputs/Outputs
Sample Input(s) | Sample Output(s) |
---|---|
The first line of input contains two integers, N and M (1 ≤ N ≤ 10, 1 ≤ M ≤ 105), indicating that a total of N valid voting ballots have been collected, and M outstanding alumni need to be selected. Following that, there will be N lines, each containing a name without spaces, representing the candidate chosen on that ballot. | Output the top M outstanding alumnus based on the number of votes they received, with one alumnus per line. Among the top M alumni, there won't be any ties in the number of votes. |
10 3 Peter James John John James James Peter Peter Peter Paul | Peter James John |
Thought Process
Use a Map to record the number of votes for each person, then use a for loop (auto it) to store the values from the Map into another array in a Pair (reversed) format. Sort the array and output the last M elements. Since M might be greater than N, this could cause a memory access error when running the for loop. Therefore, the termination condition of the for loop can be written as max(0, array length - M), so if M is greater than N causing the termination condition to be negative, it will be changed to 0 to avoid memory access errors.
Sample Code-ZeroJudge M702: Outstanding Alumnus
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
pair<int, string>rtn(int a, string b)
{
pair<int, string>tmp;
tmp.first = a;
tmp.second = b;
return tmp;
}
int main() {
int N, M;
cin >> N >> M;
map<string, int>MAP;
for (int i = 0; i<N; i++)
{
string tmp;
cin >> tmp;
MAP[tmp]++;
}
vector<pair<int, string>>v;
for (auto it:MAP)
{
v.push_back(rtn(it.second, it.first));
}
sort(v.begin(), v.end());
for (int i = int(v.size())-1; i>=max(0, int(v.size())-M); i--)
{
cout << v[i].second << " ";
}
cout << "\n";
}
//ZeroJudge M702
//Dr. SeanXD