【L2-019 悄悄关注 】天梯赛L2系列详解

天梯赛L2-019 悄悄关注 题目详情：

输入样例1：

10 GAO3 Magi Zha1 Sen1 Quan FaMK LSum Eins FatM LLao 
8
Magi 50
Pota 30
LLao 3
Ammy 48
Dave 15
GAO3 31
Zoro 1
Cath 60

输出样例1：

Ammy
Cath
Pota

输入样例2：

11 GAO3 Magi Zha1 Sen1 Quan FaMK LSum Eins FatM LLao Pota 
7
Magi 50
Pota 30
LLao 48
Ammy 3
Dave 15
GAO3 31
Zoro 29

输出样例2：

Bing Mei You

思路:

这个题目拿到手中是第一感觉是非常简单的，我的第一想法：用set存放关注的列表，用结构体存一下点赞的信息，再用set去存储筛选玩的结果然后一一输出。

很不幸超时了。

为什么超时呢？用结构体去存10000个数据，而时间限制只有150ms，很明显容易超时。

那么想一想其他的数据结构有没有可以存放点赞信息的，不难发现点赞信息是一一对应的关系，所以用map容器啊！map容器的内部是用红黑树实现的，肯定不能超时,正好可以拿这个题目来练习一下map。

详细代码:

#include
using namespace std;

int n,m;
map<string,int>mp;//存放点赞信息
set<string>s;//存放关注列表
int main()
{
    cin>>n;
    string c;
    for(int i = 0; i < n; i++)
    {
        cin>>c;
        s.insert(c);
    }
    cin>>m;
    int sum = 0, temp;//点赞的总数量和每次点赞的数量
    for(int i = 0; i < m; i++)
    {
        cin>>c>>temp;
        mp[c] = temp;
        sum += temp;
    }
    
    int avg = sum/m, num = 0;//点赞的平均数和输出的人数
    for(auto it = mp.begin(); it != mp.end(); it++)//迭代器
    {
    	if(!s.count(it->first) && it->second > avg)//不在关注列表里and点赞数量大于平均数
		{//知识点总结里面介绍it->first
			num++;
			cout<<it->first<<endl;
		} 
	}
    if(!num) //如果没有输出一个人
        cout<<"Bing Mei You"<<endl;
}

知识总结:

总结一下mao容器：
先来看一下百度百科的定义：

Map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据处理能力，
由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。

map内部数据的组织，map内部自建一颗红黑树（一种非严格意义上的平衡二叉树），
这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的

总结一下map的特点： 一 一对应，自动排序，关键字不重复（是不是和set有点像）

接下来就是map的函数：

函数之前先说一下它的关键字（又称键值）和关键字的内容（我感觉用关键字的值不太准确）
map的关键字为key，关键字的内容为value
使用时，如果要获取关键字可以直接map->key/map->first，
如果要获取关键字的内容map->value/map->second
此外，map的使用绝不仅仅只有map/map
还有map,string>/map,int>等等。

（我的意思就是说，它的关键字可以用其他的容器）

map<string,int>mp;
1.map的插入：
(1)利用insert函数
mp.insert("aaaa",1);//要和map里面的数据类型一一对应
(2)数组方式
mp[aaaa] = 1;
2.map的删除
利用函数erase()
mp.erase("aaaa");//删除关键字为aaaa的元素
3.map的遍历：
利用正向迭代器/反向迭代器（如果不理解迭代器，可以简单地把它当作指针一样的存在）
for(auto it = mp.begin(); it != mp.end(); it++)//正向
for(auto it = mp.rbegin(); it != mp.rend(); it++)//反向
4.map的大小：
int mapsize = mp.size();
5.数据查找
(1)count函数：判断关键字key是否存在,存在返回1，否则返回0
mp.count(key);
(2)find函数：找到关键字key所在的位置，但返回的是一个迭代器，找到就返回位置所在的迭代器，否则就返回mp.end()
map<int,string>::iterator iter;//定义一个迭代器，auto和它的作用一样的
iter = mp.find(key)
if(iter != mp.find())//如果if起作用了就说明找到了
使用方法同vector和set容器
简单总结一下常用的函数，然后是还有一个容器是multimap，它和map的区别就是它的关键字可以重复