E - Range Minimum Queries AtCoder Regular Contest 098

問題概略
長さNの数列Aと整数Kが与えられる。
以下の操作をQ回行う
連続するK個を選び最小値を取り除く。

上の操作で得られた最大値と最小値の差を最小にしたい。

制約
1 <= N <= 2000
1 <= A <= 10^9

解法
問題をそのまま捉えるとよくわからなくなる。
これは一番いい最大値と最小値を選ぶ問題だが、それは片方を固定すると簡単になることが多い。
例えば最小値をxにすると決めると、x未満の物が含まれる区間は選べなくなる。ここで連続する区間に対して操作をするため、いくつかのx以上の区間で独立して考えることが出来る。それらの中で得られる物を小さい順にQ個選べば良い。

問題の芯
２つの値を考える時は片方固定

public static void solve() throws Exception {
        //longを忘れるなオーバーフローするぞ
        N = ni();
        int K = ni();
        int Q = ni();
        A = nia(N);
        PriorityQueue<Integer> que = new PriorityQueue<>();
        ArrayList<Integer> lis = new ArrayList<>();
        for (int m = 0; m < N; m++) {
            que.clear();
            int min = A[m];
            for (int i = 0; i < N; ) {
                lis.clear();
                int len = 0;
                while (i < N && A[i] < min) i++;
                while (i < N && A[i] >= min) {
                    lis.add(A[i]);
                    i++;
                    len++;
                }
                Collections.sort(lis);
                for (int j = 0; j < len - K + 1; j++) {
                    que.add(lis.get(j));
                }
            }
            if (que.size() < Q) continue;
            int max = -1;
            for (int i = 0; i < Q; i++) {
                max = Math.max(max, que.poll());
            }
            chMin(max - min);
        }
        System.out.println(minRes);
    }