[PAT-A] 1129 Recommendation System

Java

import java.io.*;
import java.util.*;

public class Main {
    static final int N = 50010;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] firstLine = br.readLine().split(" ");
        int n = Integer.parseInt(firstLine[0]);
        int k = Integer.parseInt(firstLine[1]);

        int[] itemFrequency = new int[N];
        List<Integer> recommendations = new ArrayList<>();
        StringBuilder sb = new StringBuilder();

        String[] items = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            int currentItem = Integer.parseInt(items[i]);

            if (i > 0) {
                sb.append(currentItem).append(":");
                for (Integer recommendation : recommendations) {
                    sb.append(" ").append(recommendation);
                }
                sb.append("\n");
            }

            itemFrequency[currentItem]++;

            if (!recommendations.contains(currentItem)) {
                recommendations.add(currentItem);
            }

            recommendations.sort((a, b) -> {
                if (itemFrequency[a] != itemFrequency[b]) {
                    return Integer.compare(itemFrequency[b], itemFrequency[a]);
                } else {
                    return Integer.compare(a, b);
                }
            });

            if (recommendations.size() > k) {
                recommendations.remove(recommendations.size() - 1);
            }
        }

        System.out.print(sb);
        br.close();
    }
}

C++

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 50010;

int n, m;
int cnt[N];
int top_k[N];

int main() {
    scanf("%d%d", &n, &m);

    int k = 0;
    for (int i = 0; i < n; ++i) {
        int id;
        scanf("%d", &id);

        if (i) {
            printf("%d:", id);
            for (int j = 0; j < k; j++) printf(" %d", top_k[j]);
            printf("\n");
        }

        bool flag = false;
        for (int j = 0; j < k; ++j)
            if (top_k[j] == id) {
                flag = true;
                break;
            }
        if (!flag) top_k[k++] = id;
        cnt[id]++;

        sort(top_k, top_k + k, [](int &a, int &b) {
            if (cnt[a] != cnt[b]) return cnt[a] > cnt[b];
            else return a < b;
        });
        k = min(k, m);
    }
    return 0;
}