思路

因为数据卡的不严，所以O(NKlog⁡K)O(NK\log K)O(NKlogK)不会超时，所以暴力是没问题的。
但如果K的数量级变大，则应当使用单调队列。单调队列应该才是这道题真正考察的点。

代码

暴力

即我们每次都对（小于等于的）K个物品进行排序。
时间复杂度：O(NKlog⁡K)O(NK \log K)O(NKlogK)

#includeusing namespace std;struct node {int id;int freq;node(int id,int freq) {this->id = id;this->freq = freq;}bool operator < (node & o) {if(freq == o.freq)return id < o.id;return freq > o.freq;}
};int main() {int n;int K;cin >> n >> K;vector freq(n +1,0);vector recommendList;for(int i = 1;i <= n;++i) {int access;cin >> access;++freq[access];bool found = false;if(i > 1) {sort(recommendList.begin(),recommendList.end());while( recommendList.size() > (unsigned int) min(i - 1, K)) {recommendList.pop_back();}printf("%d:", access);for(auto & e: recommendList) {printf(" %d", e.id);}int size = recommendList.size();for(int j = 0; j < size; ++j) {if(recommendList[j].id == access) {recommendList[j].freq++;found = true;break;}}printf("\n");}if(!found) {recommendList.emplace_back(node{access,freq[access]});}}
}

单调队列

当队列不满k个，新物品可以直接入队。当队列已满k个，则需要反复调整当前新插入物品的位置直至合适（入队规则即为题意所示），vis用于记录队内有哪些物品。
时间复杂度：O(NK)O(NK)O(NK)
空间复杂度：O(N+K)O(N + K)O(N+K)

#includeusing namespace std;int main() {int n, k;cin >> n >> k;vector recommend(n);vector clicks(n + 1);for(int i = 0; i < n; ++i)cin >> recommend[i];vector q;map vis;vis[recommend[0]] = 0;q.push_back(recommend[0]);clicks[recommend[0]]++;for(int i = 1; i < n; ++i) {printf("%d: ", recommend[i]);int qlen = q.size();for(int i = 0; i < min(qlen, k); ++i) {printf("%d", q[i]);if(i != min(qlen, k) - 1)printf(" ");}printf("\n");clicks[recommend[i]]++;int j;if(vis.count(recommend[i])) {j = vis[recommend[i]];} else {q.push_back(recommend[i]);j = q.size() - 1;}while(j > 0 && (clicks[q[j]] > clicks[q[j-1]]|| clicks[q[j]] == clicks[q[j-1]] && q[j] < q[j-1])) {swap(q[j], q[j-1]);--j;}qlen = q.size();vis.clear();for(int k = 0; k < qlen; ++k) {vis[q[k]] = k;}while(q.size() > k) {q.pop_back();}}
}