河北大学程序设计训练营

Day11 每日一题讲解

题目

7-4 悄悄关注 (25分)

新浪微博上有个“悄悄关注”，一个用户悄悄关注的人，不出现在这个用户的关注列表上，但系统会推送其悄悄关注的人发表的微博给该用户。现在我们来做一回网络侦探，根据某人的关注列表和其对其他用户的点赞情况，扒出有可能被其悄悄关注的人。

输入格式：

输入首先在第一行给出某用户的关注列表，格式如下：

1
人数N 用户1 用户2 …… 用户N

其中N是不超过5000的正整数，每个用户i（i=1, …, N）是被其关注的用户的ID，是长度为4位的由数字和英文字母组成的字符串，各项间以空格分隔。

之后给出该用户点赞的信息：首先给出一个不超过10000的正整数M，随后M行，每行给出一个被其点赞的用户ID和对该用户的点赞次数（不超过1000），以空格分隔。注意：用户ID是一个用户的唯一身份标识。题目保证在关注列表中没有重复用户，在点赞信息中也没有重复用户。

输出格式：

我们认为被该用户点赞次数大于其点赞平均数、且不在其关注列表上的人，很可能是其悄悄关注的人。根据这个假设，请你按用户ID字母序的升序输出可能是其悄悄关注的人，每行1个ID。如果其实并没有这样的人，则输出“Bing Mei You”。

输入样例1：

1
2
3
4
5
6
7
8
9
10
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：

1
2
3
Ammy
Cath
Pota

输入样例2：

1
2
3
4
5
6
7
8
9
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：

1
Bing Mei You

题目分析

本题的主要考点是set和map的应用。首先我们要获得用户的关注列表，思考一下我们用什么数据结构存储比较好：这个关注列表我们仅仅只是用来记录这个用户是不是被显式关注的用户，换句话说，我们只关心某一个用户名是否在这个名单中，在这种情况下，用vector就杀鸡用牛刀了，对每一个元素使用find函数（algorithm库）的时间复杂度为O(n^2)，显然，使用set是更合适O(nlogn)。在我们储存完了之后我们需要获取用户的点赞信息，同时计算点赞的和，方便计算平均值。在输入的过程中同时判断当前用户是否是被显式关注的，如果不是的话就把它放在一个map里（由于是要升序输出，而map默认是有序的）。最后遍历map，如果点赞数大于平均值就把它输出出来，如果都不大于，直接输出“Bing Mei You”就可以啦！

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
#include<set>
#include<map>
using namespace std;
int main(){
    int N;cin>>N;
    set<string>user;
    for(int i=0;i<N;i++){
        string temp;cin>>temp;
        user.insert(temp);
    }
    int M;cin>>M;
    map<string,int >mp;
    int sum=0;
    for(int i=0;i<M;i++){
        string name;
        int times;
        cin>>name>>times;
        sum+=times;
        if(user.count(name)==0){
            mp[name]=times;
        }
    }
    bool qiao=false;
    double avarange=(double)sum/(double)M;
    for(auto it=mp.begin();it!=mp.end();it++){
        if(it->second>avarange){
            cout<<it->first<<endl;;
            qiao=true;
        }
    }
    if(!qiao){
        cout<<"Bing Mei You"<<endl;
    }
}