题解：P12333 n 方排序

SLBZ1 · 2025-04-26 10:53:38 · 题解

若要将区间 [l,r] 升序排序，要满足区间以外的数处于升序状态，我们可以建立两个变量 l(left),r(right) 来表示当前区间 [l,r] 将要进行升序排序，那么我们可以刚开始时将 l,r 位于 a 数组的两端，即 l=1,r=n. 如果该数为已排序的，缩小 l,r 的范围，如果该数为未排序的，那么从此数开始，以后的数都需要排序，所以就退出循环。

        for(int i=1;i<=n;i++){  //l遍历a数组 
            if(a[i]==i) l++;
            if(a[i]!=i) break;
        }
        for(int i=n;i>=1;i--){  //r遍历a数组 
            if(a[i]==i) r--;
            if(a[i]!=i) break;
        }

如果整个数列皆为升序排序，即 l,r 都遍历完时，lastans 设为 0 并输出，否则输出代价 (r−l+1)^2。

        if(l==n&&r==1){  
            lastans=0;
        }else{
            lastans=(r-l+1)*(r-l+1);
        }
        cout<<lastans<<endl; 

AC CODE

#include<bits/stdc++.h>
using namespace std;
int n,q;  //长度为n的排列    有q次变换
int a[5005];
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];   
    int lastans=0;   //设lastans表示上一次询问的答案 
    while(q--){  //q次变换 
        int x,y;
        cin>>x>>y;
        swap(a[(x-1+lastans)%n+1],a[(y-1+lastans)%n+1]);//根据题目要求交换 
        int l=1,r=n;
        for(int i=1;i<=n;i++){  //l遍历a数组 
            if(a[i]==i) l++;
            if(a[i]!=i) break;
        }
        for(int i=n;i>=1;i--){  //r遍历a数组 
            if(a[i]==i) r--;
            if(a[i]!=i) break;
        }
        if(l==n&&r==1){  //特殊处理 
            lastans=0;
        }else{
            lastans=(r-l+1)*(r-l+1);
        }
        cout<<lastans<<endl;  //记加回车 
    }
    return 0;
}