【PTA题目解答】7-4 数气球 （20分）

1.题目

天空上有n个气球，第i个气球的颜色为colori​（为全由小写字母组成的字符串）
请你数出每种颜色的气球的数量，并按照颜色出现的先后顺序进行排序输出。

输入格式:

测试数据有T组(1≤T≤100)。
对于每组样例，第一行一个整数n (1≤n≤1×105)表示气球个数。
接下来接下来n行，每行一个仅有小写字母构成的字符串colori​ (1≤∣colori​∣≤50)，代表气球的颜色。

输出格式:

对于每个样例，一种颜色的气球统计结果一行，先输出颜色，用空格隔开后输出该种颜色的气球的数量。

输入样例:

在这里给出一组输入。例如：

2
3
red
red
blue
4
ovo
vvv
ov
ovo

输出样例:

在这里给出相应的输出。例如：

red 2
blue 1
ovo 2
vvv 1
ov 1

代码：

#include <iostream>
#include <map>
#include <utility>
#include <vector>
using namespace std;int n,T;
typedef pair<string, int> PII;void print(vector<PII> & v)
{for(auto &p : v){cout << p.first << " " << p.second << '\n';}
}int Find(vector<PII> &v, string s)
{for(int i = 0; i < v.size(); ++i){if (v[i].first == s) return i;}return -1;
}int main()
{cin >> T;while(T--){int n; cin >> n;vector<PII> v;for(int i = 0; i < n; ++i){string s; cin >> s;int k = Find(v, s);if (k != -1) v[k].second++;else v.push_back({s, 1});     }print(v);}return 0;
}

扩展（根据value值进行排序）

#include <iostream>
#include <map>
#include <utility>    // pair
#include <algorithm>  // sort 
#include <vector>
using namespace std;int n, T;
typedef pair<string, int> PII;void print(vector<PII>& v)
{for (auto& p : v){cout << p.first << " " << p.second << '\n';}
}struct cmp_by_value {bool operator()(const PII &p1, const PII &p2){return p1.second > p2.second;}
};int main()
{cin >> T;while (T--){int n; cin >> n;map<string, int> mp;for(int i = 0; i < n; ++i){string s; cin >> s;mp[s]++;}//把map中元素转存到vector中vector<PII> v(mp.begin(), mp.end());sort(v.begin(), v.end(), cmp_by_value());print(v);}return 0;
}