AtCoder Regular Contest 098 : E - Range Minimum Queries
-
問題
長さ N の数列 A から「長さ K の連続する部分列を1つ選び、その中の最小値を数列から取り除く」動作を Q 回行う。Q 回で取り除いた Q 個の数値の最大値と最小値の差の最小値を求める問題。
-
解法
最小値を固定させると、まず、固定させた最小値より小さい要素は取ってはいけないので、固定させた最小値より小さい要素を含まない部分列を列挙する。その後、それぞれの部分列をソートし、その中で最大値として考えられるものを全て列挙し、最大値の候補をソートし Q 番目に小さいものを最大値とする。最初に決める最小値を A_0 ~ A_N まで試した中で、最大値と最小値の差が一番小さいものを出力すればよい。最大値を固定させてもできる。
-
解答
Submission #2716762 - AtCoder Regular Contest 098