[伯俊]#1700マルチタスクスケジューリング

質問する

寮に住むジュンギュは多機能タグを使っている.ジュンギュはキーボード、ドライヤー、携帯電話の充電器、デジタルカメラの充電器など複数の電気用品を使用しながら、各種電気製品のプラグを抜いて差し込まざるを得なかった.そこで、ジュンギュは自分の生活パターンを分析し、自分が使っている電気用品の使用順序を見つけ、それをもとにプラグを抜く回数を減らす方法を提案し、より快適な生活環境を創造した.
例えば、3つの穴(3つの穴)のマルチタブを使用する場合、電気器具の使用順序は以下のようになります.

キーボード

スタイリスト

携帯充電器

デジカメ充電器

キーボード

スタイリスト

キーボード、ドライヤー、携帯電話の充電器のプラグを複数のラベルに順番に差し込み、デジカメの充電器のプラグを差し込む前に携帯電話の充電器のプラグを抜くのがベストなので、プラグは一度だけ抜くだけです.

入力

第1行は、マルチメータ穴の個数N(1≦N≦100)と、電気用品の総使用回数K(1≦K≦100)とを整数として与える.2行目では、電気用品の名前はK以下の自然数で、使用順で与えられます.各行のすべての整数はスペースで区切られています.

しゅつりょく

次から次へとプラグを抜く最小回数を出力してください.

入力例1

2 7
2 3 2 3 1 2 7

サンプル出力1

2

に答える

この問題はよく考えた上で解決したものだ.まず、複数のラベルが空の場合は、複数のラベルを直接挿入し、アルゴリズムは複数のラベルがいっぱいになった後に非常に重要です.複数のラベルに位置がない場合は、まず後で使用しないデバイスを削除し、いずれも後で使用する場合は、最も遅く使用したデバイスを抜いてください.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;

public class Main {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int K = Integer.parseInt(input[1]);
        int[] arr = new int[K];
        HashSet<Integer> set = new HashSet<>(N);		//멀티탭

        input = br.readLine().split(" ");
        for(int i=0; i<K; i++)
            arr[i] = Integer.parseInt(input[i]);

        int idx = 0;
        int cnt = 0;

        while(idx<K) {
            int num = arr[idx];

            if(set.size()<N) {		//멀티탭에 자리가 있을 경우
                set.add(num);
                idx++;
                continue;
            }

            if(set.contains(num)) {		//이미 꽂혀있는 경우
                idx++;
                continue;
            }

            int idx2 = -1;
            int num2 = -1;
            loop:for(int x : set) {
                int i = idx+1;

                for(; i<K; i++) {
                    if(arr[i]==x) {
                        if(idx2<i) {
                            idx2 = i;
                            num2 = x;
                        }

                        continue loop;
                    }
                }

                num2 = x;
                break;
            }

            set.remove(num2);
            set.add(num);
            cnt++;
            idx++;
        }

        System.out.println(cnt);
    }
}