AtCoder Regular Contest 098 E - Range Minimum Queries

题目链接https://arc098.contest.atcoder.jp/tasks/arc098_c

题意:给你一个序列,你可以进行q次操作,每次操作选连续一段长度为k的子区间,然后从这个子区间中删去最小的数,目标是最小化q次操作后的Y-X,其中X代表你删除所有数中的最小的数,Y代表你删除所有数中最大的数。

思路:两个变量在变的时候要学会固定一个变量,所以我们枚举序列的每个值a_i,以它作为删除所有数中的最小值,那么我们可以发现因为这个限制,我们可操作的有效区间变成了若干段,然后每一段就可以随便操作了。又因为我们想最小化Y,所以每一段我们把尽量小的加入到一个临时数组里,最后对这个数组排个序然后取出第q小的就可以了,时间复杂度O(n^2log n),据说有O(nlogn)的做法不过我也不会啊。。。

#include <bits/stdc++.h>
using namespace std;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=2000+10;
int n,K,q,i,j,k,cnt,a[N],b[N],res[N];
int main(){
    read(n),read(K),read(q);
    for (i=1;i<=n;i++) read(a[i]);
    int ans=1000000000+7;
    for (i=1;i<=n;i++){
        int l=0;
        for (cnt=0,j=1;j<=n+1;j++){
            if (a[j]<a[i]){
                if (!l) continue;
                int r=j-1;
                for (k=l;k<=r;k++) b[k]=a[k];
                sort(b+l,b+r+1);
                for (k=l;k+K-1<=r;k++) res[++cnt]=b[k];
                l=0;
            }
            else if (!l) l=j;
        }
        if (cnt<q) continue;
        sort(res+1,res+cnt+1);
        ans=min(ans,res[q]-a[i]);
    }
    printf("%d\n",ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注