文文母校適逢百年校慶,校友會舉辦「傑出校友票選活動」。在回收了所有的校友選票之後,交給你來協助統計票數。
範例測資
範例輸入 | 範例輸出 |
---|---|
輸入的第一行含有兩個整數 N 和 M (1 ≤ N ≤ 10,1 ≤ M ≤ 105),代表一共回收 N 張有效選票,要選出 M 個傑出校友。 接下來會有 N 行,每行有一個不含空白的名字,代表該張選票所投給的對象。 | 依得票數高低,輸出得票最高的 M 個傑出校友於一行。前 M 名的傑出校友中不會有得票數相同的情況。 |
10 3 Peter James John John James James Peter Peter Peter Paul | Peter James John |
解題思路
使用 Map 來紀錄每個人的得票數,再來使用 for (auto it:Map),將 Map 中的值改用Pair (倒過來) 的方式存到另外一個陣列中。將陣列 Sort 過後將陣列位置最後M個資料做輸出,有可能M會比N還要大,這樣會在跑For迴圈的時候造成記憶體區段錯誤,所以 For 迴圈的終止條件可以寫成 max(0, 陣列長度-M),這樣如果M比N大造成終止條件為負數時,終止條件會改成0避免記憶體區段錯誤。
範例程式碼-ZeroJudge M702: 傑出校友票選活動
#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