h3c路由器怎么做网站映射如何进行网络推广和宣传

博主欢迎转载，但请给出本文链接，我尊重你，你尊重我，谢谢~
http://www.cnblogs.com/chenxiwenruo/p/6789819.html
特别不喜欢那些随便转载别人的原创文章又不给出链接的
所以不准偷偷复制博主的博客噢~~

 

题意：用户每次选择一个indice，输出之前出现的频率最高的k个indice
如果恰好有两个频率一样，输出indice较小的那个

显然不能每次都要对当前所有的item排个序，会超时的
由于每次只要给出前k个出现频率最高的，如果出现频率一样，则给出值最小的
所以只要能存储前k个item的出现频率和值就行

用户每查询一个indice，先对当前的recommend进行排序，输出k个，不足k个的有多少输出多少，然后进行更新操作。
如果indice在当前的recommend里，那么只要更新下频率即可
如果不在的话，那么就要分情况了
如果当前recommend不足k个，那么往后添加一个新的即可
如果当前recomend已经有k个，只要将新的indice与最后一个进行比较与替换即可

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=50000+5;
int cnt[maxn];
int n,k;struct Node{int indice;int cnt;bool operator<(const Node tmp)const{if(cnt==tmp.cnt){return indice<tmp.indice;}else{return cnt>tmp.cnt;}}
}recommend[10+5];
int main()
{int indice;int len;Node node;memset(cnt,0,sizeof(cnt));scanf("%d %d",&n,&k);if(n>=1){scanf("%d",&indice);cnt[indice]++;node.cnt=cnt[indice];node.indice=indice;recommend[0]=node;len=1;}for(int i=1;i<n;i++){scanf("%d",&indice);printf("%d:",indice);//当len<k的时候，若没在len个里面出现过，往recommend数组后面添就行if(len<k){sort(recommend,recommend+len);bool isExist=false;int idx;for(int j=0;j<len;j++){printf(" %d",recommend[j].indice);if(recommend[j].indice==indice){isExist=true;recommend[j].cnt++;cnt[indice]++;}}if(!isExist){recommend[len].indice=indice;recommend[len].cnt=cnt[indice]=1;len++;}}//如果recommend已经有k个了，那么如果在这k个里面没出现过，当前的就得和第k个比较了else{sort(recommend,recommend+k);bool isExist=false;int idx;for(int j=0;j<k;j++){printf(" %d",recommend[j].indice);if(recommend[j].indice==indice){isExist=true;recommend[j].cnt++;cnt[indice]++;}}if(!isExist){cnt[indice]++;if(cnt[indice]>recommend[k-1].cnt ||(cnt[indice]==recommend[k-1].cnt && indice<recommend[k-1].indice)){recommend[k-1].cnt=cnt[indice];recommend[k-1].indice=indice;}}}printf("\n");}return 0;
}