L2-019 悄悄关注 题解

L2-019 悄悄关注

链接：题目详情 - L2-019 悄悄关注 (pintia.cn)

思路：

自己写了两个方法，先说通过了的。

方法一 用两个string映射到int的map,一个记录关注列表，一个记录点赞情况。输入的时候记录点赞总数算平均值，然后遍历点赞情况的map，如果值大于平均数且键没有在关注列表中的话，就直接输出；如果没有这样的数据，就输出“并没有”。

代码量少，但是复杂度大。（30ms）

#include <iostream>
#include <string>
#include <map>
#include <vector>
using namespace std;
string s;
map<string, int> guanzhu,zan;
int N,M;
int main(){
    int i,x;
    cin>>N;
    for(i=0;i<N;i++){
        cin>>s;
        guanzhu[s]=1;
    }
    cin>>M;
    int sum=0;
    for(i=0;i<M;i++){
        cin>>s>>x;
        zan[s]=x;
        sum+=x;
    }
    sum=sum/M;
    int Y=0;
    for(map<string,int>::iterator it=zan.begin();it!=zan.end();it++){
        if(it->second > sum&&guanzhu[it->first]!=1){
            Y=1;
            cout<<it->first<<endl;
        }
    }
    if(Y==0)
        cout<<"Bing Mei You";
}

方法二 灵感来源于小字辈那题看的大佬的代码，认为二重的vector数组可以极大的降低时间复杂度（事实上也是这样），所以碰见这题的时候就想先用这个。一个string映射到int的map记录关注列表，一个二维的string的vector数组记录点赞情况，行号作为点赞量，列中的元素记录人名，vector数记得要扩容！从大于平均值的行号开始向下遍历vector数组，并将没在关注列表的元素加入到set中等待输出。最后输出set，如果set长度是0，输出“并没有”。

代码量稍微大一些，但是时间复杂度小很多！（10ms）

#include <iostream>
#include <string>
#include <map>
#include <set>
#include <vector>
using namespace std;
string s;
vector<vector<string> > xin;
map<string, int> guanzhu;
set<string> shu;
int N,M;
int main(){
    int i,x;
    xin.resize(1001);
    cin>>N;
    for(i=0;i<N;i++){
        cin>>s;
        guanzhu[s]=1;
    }
    cin>>M;
    int sum=0;
    for(i=0;i<M;i++){
        cin>>s>>x;
        xin[x].push_back(s);
        sum+=x;
    }
    sum=sum/M;
    for(vector<string>::size_type j=sum+1;j<1000;j++){
        for(vector<string>::size_type k=0;k<xin[j].size();k++){
        	if(guanzhu[ xin[j][k] ]!=1)
                shu.insert( xin[j][k] );
		}
    }
    for(set<string>::iterator it=shu.begin();it!=shu.end();it++){
        cout<<*it<<endl;
    }
    if(shu.size()==0)
        cout<<"Bing Mei You";
}