本文主要是介绍[CF1696D]Permutation Graph 题解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

传送门(*╹▽╹*)

Preface

这是官方的 \(O(N)\) 做法，个人感觉十分优美，故记录下来。

Analysis

显然，直接建图跑最短路不可行，但我们可以转向思考必须经过的点。

容易发现，若 \(a_i = n\)，那么从 \(1\) 到 \(n\) 的路径上必须要经过点 \(i\)。

考虑将 \((1,n)\) 分割成 \((1,i - 1)\) 和 \((i+1,n)\) 两部分处理。

以 \((1,i-1)\) 的部分为例，我们会发现并不需要再求出 \((1,i-1)\) 的最大最小值。

因为我们有了 \(a_i=n\)，所以我们只需在 \((1,i-1)\) 中取一个使得 \(a_j\) 最小的 \(j\) 即可。

接下来就是再次分割为 \((1,j-1)\) 和 \((j+1,i)\) 处理。

\((i+1,n)\) 的部分也是同理。

可以发现这个过程并不需要任何数据结构维护，只需要前缀和后缀的最大最小值数组。

在一开始找出 \(i\) 的位置，分两次循环往 \(1\) 和 \(n\) 扫一遍就行了。

时间复杂度 \(O(N)\)。感到有点疑惑的话可以参考我的代码。

Code

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 5;
int n,a[maxn],pre[maxn][2],suf[maxn][2];
//0:minimum
//1:maximum
void work() {
    scanf("%d",&n);
    for(int i = 1;i <= n;++ i)scanf("%d",&a[i]);
    pre[1][0] = pre[1][1] = a[1];
    for(int i = 2;i <= n;++ i)pre[i][0] = min(pre[i - 1][0] , a[i]),pre[i][1] = max(pre[i - 1][1] , a[i]);
    suf[n][0] = suf[n][1] = a[n];
    for(int i = n - 1;i;-- i)suf[i][0] = min(suf[i + 1][0] , a[i]),suf[i][1] = max(suf[i + 1][1] , a[i]);
    int mid = 1,cnt = 1;
    for(int i = 2;i <= n;++ i) {
        if(a[i] == n) {
            mid = i;
            break ;
        }
    }
    bool cur = 0;
    int lst = mid;
    for(int i = mid - 1;i;-- i) {
        if(a[i] == pre[lst - 1][cur]) {
            ++ cnt;
            lst = i;
            cur ^= 1;
        }
    }
    lst = mid;
    cur = 0;
    for(int i = mid + 1;i <= n;++ i) {
        if(a[i] == suf[lst + 1][cur]) {
            ++ cnt;
            lst = i;
            cur ^= 1;
        }
    }
    printf("%d\n",cnt - 1);
    return ;
}
int main() {
    int T;
    scanf("%d",&T);
    while(T --)work();
    return 0;
}

完结撒花✿✿ヽ(°▽°)ノ✿

这篇关于[CF1696D]Permutation Graph 题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！