PATA1129题解

//
//  main.cpp
//  PATA1129
//
//  Created by Phoenix on 2018/2/25.
//  Copyright © 2018年 Phoenix. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 50010;
int n, k;
int num[maxn] = {0};        //记录已经出现的次数

int main(int argc, const char * argv[]) {
    scanf("%d %d", &n, &k);
    int a, t = 0;               //t为目前要推荐的个数
    int rank[11] = {0};         //记录当前推荐的顺序
    scanf("%d", &a);            //记录第一个元素
    num[a]++;
    rank[0] = a;
    t++;
    for(int i = 1; i < n; i++) {
        scanf("%d", &a);
        printf("%d:", a);
        for (int j = 0; j < k && j < t; j++) {
            printf(" %d", rank[j]);
        }
        num[a]++;
        int s = t, u = t;
        for(int j = t - 1; j >= 0; j--) {
            if(num[a] > num[rank[j]]) s = j;        //如果a的数量比第j位的数量多，a排在第j位推荐，找到最小的j
            if(num[a] == num[rank[j]] && a < rank[j]) s = j;    //或者a的数量与第j位的数量相等且a的值比第j位的值小，a排在第j位推荐
            if(rank[j] == a) u = j; //寻找a是否本来就在被推荐队列中
        }
        if(u < t) {             //如果a在被推荐队列中
            if(s < u){          //如果s比原先位置小，将s到u的元素依次向后移动
                int temp = rank[u];
                for(int j = u; j > s; j--) {
                    rank[j] = rank[j - 1];
                }
                rank[s] = temp;
            }
        } else {            //如果a不在被推荐队列
            if(t < k) {     //如果当前被推荐个数小于k
                rank[t++] = a;
                int p = t - 1;
                for(int j = t - 1; j >= 0; j--) {   //寻找rank[j]的数量为1且a比rank[j]的值小的最小位置，并将元素依次后移
                    if(num[rank[j]] == 1 && a < rank[j]) p = j;
                }
                for(int j = t - 1; j > p; j--) {
                    rank[j] = rank[j-1];
                }
                rank[p] = a;
            } else if(s < t) {      //如果s的位置小于t且t == k，但a不在推荐队列中
                for(int j = t - 1; j > s; j--) { //直接将s开始的元素依次长、后移，并将rank[s] = a
                    rank[j] = rank[j - 1];
                }
                rank[s] = a;
            }
        }
        printf("\n");
    }
    return 0;
}