PAT 1129

题目 ： Recommendation System

分值 ： 25
难度 ： 中等题
思路 ： 一开始怕麻烦利用求K个最大的数（因为觉得K比较小,但超时） 然后就动态更新推荐名单
坑点 ： 考算法题，在时间上会卡你，所以动态更新推荐名单才不会超时

具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <algorithm>
using namespace std;
int data[50001] ;
int flag[50001] ;
int N ,K ;
typedef struct Node
{
    int self;
    int count = 0 ;
}Nodes ;
Nodes Q[10] ;
int cur = 0 ;
bool cmp(Node a , Node b)
{
    if(a.count == b.count )
        return a.self < b .self ;
    return
        a.count > b.count ;
}
void change_(int x)
{
    if(flag[x])
    {
        for(int i = 0 ; i< K ; i++)
            if(Q[i].self == x)
            {
                Q[i].count ++ ; break ;
            }
    }
    else
    {
        if(cur < K )         //如果队列未满 则新加入的 x 直接可以进入队列
        {
            Q[cur].self = x;
            Q[cur].count = data[x] ;
            cur ++ ;
            flag[x] = 1 ;  // 标记 x在 队列中
        }
        else if(cur == K)     // 如果队列满了
        {
            if(Q[K-1].count < data[x] || (Q[K-1].count== data[x] && x < Q[K-1].self ) )
            {
                flag[ Q[K-1].self ]=  0;
                flag[x] = 1 ;
                Q[K-1].self = x ;
                Q[K-1].count = data[x] ;
            }
        }
    }

}
void print()
{
    sort(Q,Q+cur ,cmp);
    for(int i= 0 ; i< cur ;i++)
        cout <<" "<<Q[i].self ;
    cout <<endl ;
}
int main() {
    cin >> N  >> K ;
    for(int i = 0 ; i< N ; i++)
    {
        int value ;
        cin >> value ;
        if(i)
        {
            cout <<value<<":";
            print();
        }
        data[value] ++ ;
        change_(value) ;
    }

}