E - Range Minimum Queries

题意：长为n的Arr,一共执行q次操作，每次操作要求删除一个长度为k的 连续区间的最小值 。 问，所有删除的数中，MAX-MIN的最小值是多少

思路：枚举MIN，寻找所有满足条件的最大值，找最大值的最小值

//#pragma comment(linker, "/stack:100000000")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define PI acos(-1.0)
#define pb push_back
#define F first
#define S second
#define debug puts
#define setp cout << fixed << setprecision(15)
#define fst ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int MOD=998244353;
int a[N],n,k,q;
int ans=1e9+9;

void cul(int mn){
    int l=1,r=1;
    int c[5000];
    int cnt=0;
    while(l<=n){

        while(l<=n&&a[l]<mn)    l++;
        r=l;
        while(r<=n&&a[r]>=mn)   r++;
        r--;
        if(r-l+1>=k){// 找到区间[L,R]，其中值都是>=mn
            int t[5000];int j=0;
            for(int i=l;i<=r;++i) t[++j]=a[i];
            sort(t+1,t+1+j);//排序取t数组中前r-l+1-k+1个最小
            j=1;
            for(int i=cnt+1;j<=r-l+1-k+1;i++,j++){
                c[i]=t[j];
            }
            cnt+=r-l+1-k+1;
        }
        l=++r;
    }
    if(cnt>=q){//如果取mn的情况下，能够执行q次操作
        sort(c+1,c+1+cnt);
        if(c[1]==mn){
            ans=min(ans,c[q]-mn);
        }
    }
}

int main(void){
    fst;
    cin >>n >>k >>q;
    for(int i=1;i<=n;i++)   cin >>a[i];
    for(int i=1;i<=n;i++)
        cul(a[i]);
    cout << ans << endl;

    return 0;
}
void bef0re_submit(){
    debug("Make sure the algorithm is right!");
    debug("LONG LONG!!!");
    debug("n==0?1?2?3?");
    debug("Make sure output format is right/// Yes??YES  (%.20LF)???");
    debug("if all meet,run with special situation!!!");
    debug("I confirm that I have done all above");

    debug("If u know brute,consider fast,binary(log) or tree?");
}