ARC098 E - Range Minimum Queries

問題

長さnの数列に対し「長さkの区間を選び、その中の最小の要素を取り除く」という操作をq回行う
取り除いた要素の最大値をx、最小値をyとしてx-yの最小値を求める

解法

最小値を決め打ちして最大値を最小化する方針
最小値をyにするには、y未満の数字を含む区間を選ぶことはできない
そこでy未満の要素を全て消すと、元の数列に穴が空き、いくつかの独立な区間に分かれる
各区間からは、区間の長さをmとすると最大で、その区間の中で小さい方からm-k+1個の数字を取り除ける
これらの取り除ける数字全ての中でq番目に小さい値をxにするのが最善

実装

しゃくとり法っぽく

int n, k, q, a[2020], res = inf;

int main() {
	cin >> n >> k >> q;
	rep(i,n) cin >> a[i];
	rep(i,n) {
		vector<int> mn;
		rep(l,n) if (a[i]<=a[l]) {
			int r = l;
			vector<int> t;
			while (r<n && a[i]<=a[r]) t.push_back(a[r++]);
			sort(all(t));
			rep(j,(int)t.size()-k+1) mn.push_back(t[j]);
			l = r-1;
		}
		sort(all(mn));
		if (mn.size()>=q) chmin(res, mn[q-1]-a[i]);
	}
	cout << res;
}