7-5 悄悄关注（PTA）使用set来高效查找

大家好，欢迎来到IT知识分享网。

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

输入格式：

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

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

解法：

思路：

传统思路，先存入数据，再进行条件判断，筛选出符合条件的数据，并按照要求的格式输出。

代码1（只有15分，发生段错误，使用多层for循环，代码繁琐）：

#include <iostream> #include <string.h> using namespace std; int main() { int N, M, num[10010], avg = 0, flag = 0,k=0; string id[5010], ID[10010],s[1000]; s[0]="并没有"; cin >> N; for (int i = 0; i < N; i++) { cin >> id[i]; } cin >> M; for (int i = 0; i < M; i++) { cin >> ID[i] >> num[i]; avg += num[i]; } avg = avg / M; for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { if (ID[i].compare(id[j]) == 0) { flag = 1; } } if (num[i] > avg && flag != 1) { s[k]=ID[i]; k++; } flag = 0; } if(s[0]=="并没有") { cout<<"Bing Mei You"<<endl; } else { for(int i=0;i<k;i++) { for(int j=0;j<k-1-i;j++) { if((s[j][0] - s[j+1][0]) > 0 ) { string temp = s[j]; s[j] = s[j+1]; s[j+1] = temp; } } } for(int i=0;i<k;i++) { cout<<s[i]<<endl; } } }

代码2（基于代码1，解决段错误问题）：

• 不手动排序，使用<algorithm>头文件中的std::sort函数。
• 将魔术数字替换为命名常量，以提高代码清晰度和可维护性。

#include <iostream> #include <string.h> #include <algorithm> using namespace std; const int MAX_N = 5010; const int MAX_M = 10010; int main() { int N, M, num[MAX_M], avg = 0, flag = 0,k=0; string id[MAX_N], ID[MAX_M], s[MAX_M]; s[0]="并没有"; cin >> N; for (int i = 0; i < N; i++) { cin >> id[i]; } cin >> M; for (int i = 0; i < M; i++) { cin >> ID[i] >> num[i]; avg += num[i]; } avg = avg / M; for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { if (ID[i].compare(id[j]) == 0) { flag = 1; } } if (num[i] > avg && flag != 1) { s[k]=ID[i]; k++; } flag = 0; } if(s[0]=="并没有") { cout<<"Bing Mei You"<<endl; } else { sort(s, s + k); for(int i=0;i<k;i++) { cout<<s[i]<<endl; } } }

代码3（基于代码2，对繁琐的多层for循环进行优化）：

• 使用set来高效查找用户 ID。

#include <iostream> #include <set> #include <vector> #include <algorithm> using namespace std; const int MAX_N = 5010; const int MAX_M = 10010; int main() { int N, M, num[MAX_M], avg = 0; string id[MAX_N], ID[MAX_M], s[MAX_M]; set<string> idSet; s[0] = "并没有"; cin >> N; for (int i = 0; i < N; i++) { cin >> id[i]; idSet.insert(id[i]); } cin >> M; for (int i = 0; i < M; i++) { cin >> ID[i] >> num[i]; avg += num[i]; } avg /= M; int k = 0; for (int i = 0; i < M; i++) { if (num[i] > avg && idSet.find(ID[i]) == idSet.end()) { s[k++] = ID[i]; } } if (s[0] == "并没有") { cout << "Bing Mei You" << endl; } else { sort(s, s + k); for (int i = 0; i < k; i++) { cout << s[i] << endl; } } return 0; }