题解：AT_abc352_d [ABC352D] Permutation Subsequence

· · 题解

D.Permutation Sequence

题意简述：

给一个从 1 到 N 的排列，从中选取值连续的 K 个数，求这些数下表最大和最小的差的最小值

sol:

容易想到暴力做法，从 1 到 n 枚举，每次扫一遍这中间包含的数的下标，求 \min，时间复杂度 O(n^2)

考虑优化，如果我们将这些数映射到一个 map 中，那么就可以通过锁定这 i 到 i+k 的区间，快速得到这些数对应的下标。但是题目实际让我们求的是一个固定区间内的最大值和最小值，中间值是没有任何用处的。这和滑动窗口很相似。所以可以用单调队列来处理。每次加入新的下标位置，这样可以让求最大值和最小值的复杂度降到 O(1)，总体时间复杂度降到 O(n)。加上 map 的复杂度是 O(n \log n)，可以通过此题。

至于单调队列的写法，这里不再赘述。有需要请左转 P1886 滑动窗口 /【模板】单调队列。

#include <iostream>
#include <cstdio>
#include <deque>
#include <map>

using namespace std;
int n, k, a[200005], maxn, minn, p;
deque<int> qMax, qMin;
map<int, int> s;
//单调队列求最大最小
void slidemax(int pos){
    while(!qMax.empty()&&qMax.front()<=pos-k) qMax.pop_front();
    while(!qMax.empty()&&s[qMax.back()]<=s[pos]) qMax.pop_back();
    qMax.push_back(pos);
}
void slidemin(int pos){
    while(!qMin.empty()&&qMin.front()<=pos-k) qMin.pop_front();
    while(!qMin.empty()&&s[qMin.back()]>=s[pos]) qMin.pop_back();
    qMin.push_back(pos);
}
int main(){
    scanf("%d%d", &n, &k);
    for (int i=1; i<=n; i++){
        scanf("%d", &a[i]);
        s[a[i]]=i; //将值和下标映射对应起来
    }
    int ans=0x3f3f3f3f;
    for (int i=1; i<=n; i++){
        slidemin(i);slidemax(i); //窗口滑动
        if(i>=k) ans=min(ans, s[qMax.front()]-s[qMin.front()]);
    }
    printf("%d\n", ans);

    return 0;
}