题意:输出top n高频出现的词和对应词出现的次数。注意一点,可能出现超出n个输出的情况,当且仅当超出部分的单词出现次数和
第n个相同。
思路:模拟。
// file name: LA6578.cpp // // author: kereo // // create time: 2014年10月15日 星期三 23时11分51秒 // //***********************************// #include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<set> #include<map> #include<vector> #include<stack> #include<cmath> #include<string> #include<algorithm> using namespace std; typedef long long ll; const int MAXN=200000+100; const int inf=0x3fffffff; const int mod=1000000000+7; #define L(x) (x<<1) #define R(x) (x<<1|1) int n; string str; vector<string>vec[7]; struct node{ int cnt; string s; }nod[MAXN]; map<string,int>mp; bool cmp(node a,node b){ if(a.cnt == b.cnt) return a.s<b.s; return a.cnt>b.cnt; } int main() { //freopen("text","r",stdin); int now=0; for(int i=0;i<7;i++) vec[i].clear(); while(cin>>str){ if(str=="<text>"){ vec[now].clear(); while(cin>>str){ if(str=="</text>") break; if(str.length()<4) continue; vec[now].push_back(str); } now=(now+1)%7; } else{ mp.clear(); int cnt=0; cin>>n>>str; printf("<top %d>\n",n); for(int i=0;i<7;i++){ for(int j=0;j<vec[i].size();j++){ int id=mp[vec[i][j]]; if(id) nod[id].cnt++; else{ mp[vec[i][j]]=++cnt; nod[cnt].s=vec[i][j]; nod[cnt].cnt=1; } } } sort(nod+1,nod+cnt+1,cmp); for(int i=1;i<=min(cnt,n);++i) cout<<nod[i].s<<" "<<nod[i].cnt<<endl; int num=nod[min(cnt,n)].cnt; for(int i=min(cnt,n)+1;i<=cnt;++i) if(nod[i].cnt==num) cout<<nod[i].s<<" "<<nod[i].cnt<<endl; printf("</top>\n"); } } return 0; }