3949303_ac_266ms_4920k.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.Scanner;
import java.util.TreeSet;

public class Main {
	
	private Scanner in;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		new Main().run();
	}
	
	private void run() {
		in = new Scanner(System.in);
		int cas;
		int n, k;
		TreeSet <Integer> ts = new TreeSet <Integer> ();
		
		cas = in.nextInt();
		for (int i = 0; i < cas; i++) {
			k = in.nextInt();
			n = in.nextInt();
			ts.clear();
			int[] dvd = new int[n];
			for (int j = 0; j < n; j++) {
				dvd[j] = in.nextInt();
			}
			int ans = 0;
			for (int j = 0; j < n; j++) {
				if (ts.contains(dvd[j])) {
					continue;
				}
				if (ts.size() < k) {
					ts.add(dvd[j]);
					ans++;
					continue;
				}
				int max = -1;
				int out = -1;
				for (int d : ts) {
					int l;
					for (l = j + 1; l < n && dvd[l] != d; l++);
					if (l > max) {
						max = l;
						out = d;
					}
				}
				ts.remove(out);
				ts.add(dvd[j]);
				ans++;
			}
			System.out.println(ans);
		}
	}

}