L2-019. 悄悄关注

时间限制

150 ms

内存限制

65536 kB

代码长度限制

8000 B

判题程序

Standard

作者

陈越

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

输入格式：

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

人数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：

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

输出样例1：

AmmyCathPota

输入样例2：

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

输出样例2：

Bing Mei You 题意：现在要找出一个用户悄悄关注的所有可能的用户。已知该用户的关注用户（并非悄悄关注），以及该用户在一段时间内给其他用户点赞的情况，如果他对某个用户点赞的次数大于对所有用户平均的点赞数，并且该用户不在关注用户的列表内，那么 这个用户就可能是一个悄悄关注的用户。 思路：对点赞情况进行排序，依据点赞次数从小到大排，那么现在就可以二分查找出比平均点赞数大的用户，对于每一个这样的用户，找一下该用户是否在关注用户的集合中出现，如果没有出现，意味着该用户可能是一个悄悄关注的用户。 AC代码：

#define _CRT_SECURE_NO_DEPRECATE#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              using namespace std;const int N_MAX = 5000 + 4, M_MAX = 10000 + 1;struct per { int first; string second; per(int first, string second) :first(first), second(second) {} bool operator <(const per&b)const { return this->first < b.first; }};vector
              
               person;//点赞的记录set
               
                table;set
                
                 Set;int Sum(vector
                 
                  a) { int sum = 0; for (vector
                  
                   ::iterator it = a.begin(); it != a.end(); it++) sum += it->first; return sum;}int main() { int N, K; scanf("%d", &N); for (int i = 0; i < N; i++) { string s; cin >> s; table.insert(s); } scanf("%d", &K); for (int i = 0; i < K; i++) { string s; int a; cin >> s; scanf("%d", &a); person.push_back(per(a, s)); } int ave = Sum(person) / K; sort(person.begin(), person.end()); string s1 = " ";//!!!! vector
                   
                    ::iterator it = upper_bound(person.begin(), person.end(), per(ave, s1));//it指针，指向比平均赞数大的人 bool what = 0, ant = 0; for (; it != person.end(); it++) { set
                    
                     ::iterator iter = table.find(it->second);//在list库中查找是否有人名it->second if (iter == table.end()) { //没有这个人 ant = 1; Set.insert(it->second); } } if (!ant)printf("Bing Mei You\n"); else { for (set
                     
                      ::iterator it = Set.begin(); it != Set.end(); it++) cout << *it << endl; } return 0;}

转载于:https://www.cnblogs.com/ZefengYao/p/6640411.html

你可能感兴趣的文章