题目描述: 微博上有个“点赞”功能,你可以为你喜欢的博文点个赞表示支持。每篇博文都有一些刻画其特性的标签,而你点赞的博文的类型,也间接刻画了你的特性。本题就要求你写个程序,通过统计一个人点赞的纪录,分析这个人的特性。 输入格式:
输入在第一行给出一个正整数N(≤1000),是该用户点赞的博文数量。随后N行,每行给出一篇被其点赞的博文的特性描述,格式为“K F1⋯FK”,其中1≤K≤10,Fi(i=1,⋯,K)是特性标签的编号,我们将所有特性标签从1到1000编号。数字间以空格分隔。 输出格式:
统计所有被点赞的博文中最常出现的那个特性标签,在一行中输出它的编号和出现次数,数字间隔1个空格。如果有并列,则输出编号最大的那个。 输入样例:
4 3 889 233 2 5 100 3 233 2 73 4 3 73 889 2 2 233 123
输出样例:
233 3
解题思路: 使用 map 容器,将输入的标签作为键插入其中,值存储标签出现的数量。输入时判断输入的标签是否存在于容器中,若存在,则对应的值 +1 ;若不存在,则向容器中添加一个以该标签为键,以 1 为值的元素(表示这个标签出现一次)。最后遍历容器,记录下值最大的元素的键和值并输出。
通关代码:
#include <iostream>
#include <map>
using namespace std;
int main() {
map<int, int> label;
int N, K, F, key = 0, num = 0;
cin >> N;
while (N--) {
cin >> K;
while (K--) {
cin >> F;
if (label.find(F) != label.end()) {
label.at(F)++;
} else {
label.insert(pair<int, int>(F, 1));
}
}
}
for (map<int, int>::iterator p = label.begin(); p != label.end(); p++) {
if (p->second >= num) {
num = p->second;
key = p->first;
}
}
cout << key << ' ' << num;
return 0;
}
通关代码:
意外收获: 起初一直觉得一个地方很奇怪:我在遍历容器取最大值对应的键和值时,我仅仅使用了判断条件 p->second >= num 就能总是取得键的最大值。 起初我觉得这不合理,我想如果使用下面这组测试数据:
2
4 3 3 3 3
4 1 1 1 1
那么 map 内存储的元素应该是这样排列的:< 3, 4 >, < 1, 4 >。(这只是我最先的猜想,是错误的)。 我就想如果 map 内的元素如上的话,仅仅使用了判断条件 p->second >= num ,那么最后结果应该输出 1 4 才对,但是测试了以后,依然输出的是正确答案 3 4。 直到输出并查看了 map 内的元素排列:< 1, 4 >, < 3, 4 >.。 我恍然大悟:map 容器内的元素会根据键的值自动进行升序排列 !这可是 map 容器的基本性质啊,看来我对于 STL 的基础还是不够牢固啊。