Passport Control

https://www.acmicpc.net/problem/16288

に答える

これは以前、icpcソウル地域予選で発生した問題だ.
初めて質問を見てQに入り、出た結果で答えを求めようとした.しかし、このようにすると、入力の結果と比較するのは難しく、状況も多いので難しいです.
結果は長い間うろうろしていた中でいくつかのヒントを見た.
コアは、入力した値を逆に実行し、キューに入れることです.Qの反対なのでスタック利用と考えられます.
このように入力値をスタックに入れ、スタック内の値より小さい値を入れると不可能と判断して「NO」を出力し、それ以外は「YES」を出力する.
また、説明はスタックであり、どうせ参照する値はスタックのtopなので、kサイズのスタック配列が1つだけ必要です.

コード#コード#

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    static int n, m, k;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        k = Integer.parseInt(input[1]);

        int[] arr = new int[n];
        String[] line = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(line[i]);
        }

        int[] tops = new int[k];

        boolean available = true;
        loop:
        for (int i = 0; i < n; i++) {
            int num = arr[i];
            for (int j = 0; j < k; j++) {
                if (tops[j] == 0 || num > tops[j]) {
                    tops[j] = num;
                    continue loop;
                }
            }
            available = false;
            break;
        }

        if(available)
            bw.write("YES");
        else
            bw.write("NO");

        bw.flush();
        bw.close();
        br.close();
    }
}