【题解】交换排序法

题意

给你一个有个不同元素的数组，你可以通过交换相邻元素的值对数组进行改变，但是数组中有个位置上的元素是不能进行主动交换的，即若存在，不能交换。问当前这个数组能否变为从大到小的顺序排列呢。

题解

首先分析到当存在一个点不能进行交换时，实际上就将数组分成了两部分，分界点的左边的元素是到不了分界点右边的，那么也就是抽象成为以个位置分成了个区间，要让数组整体从大到小排序，也就是所对每个区间内的排完序后数组能实现整体有序，那么现在分析两个相邻区间需要满足什么，也就是左区间中的最小值要大于右区间中的最大值，且每个分界点都要满足那么整体就能实现从大到小排序了。我们可以预处理出前缀的最小值和后缀的最大值，然后就可以的判断分界点两端左边区间最小值是否大于右边区间最大值了。

复杂度

时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int MAX=0x3f3f3f3f;
int a[N],maxn[N],minn[N];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,k;
        scanf("%d%d",&n,&k);
        for(int i=1; i<=n; i++)
            scanf("%d",&a[i]);
        minn[0]=MAX;
        maxn[n+1]=0;
        for(int i=1; i<=n; i++)
            minn[i]=min(a[i],minn[i-1]);
        for(int i=n; i>=1; i--)
            maxn[i]=max(a[i],maxn[i+1]);
        int flag=1;
        for(int i=0;i<k;i++)
        {
            int x;
            scanf("%d",&x);
            if(minn[x]<maxn[x+1])
                flag=0;
        }
        if(flag)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}