专栏文章

题解：P12333 n 方排序

SSLBZ1
P12333题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miphxob4
此快照首次捕获于
2025/12/03 12:17
3 个月前
此快照最后确认于
2025/12/03 12:17
3 个月前
查看原文
若要将区间 [l,r][l,r] 升序排序，要满足区间以外的数处于升序状态，我们可以建立两个变量 l(left),r(right)l(left),r(right) 来表示当前区间 [l,r][l,r] 将要进行升序排序，那么我们可以刚开始时将 l,rl,r 位于 a 数组的两端，即 l=1,r=n.l=1,r=n. 如果该数为已排序的，缩小 l,rl,r 的范围，如果该数为未排序的，那么从此数开始，以后的数都需要排序，所以就退出循环。
CPP
        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,rl,r 都遍历完时，lastans 设为 0 并输出，否则输出代价 (r−l+1)2(r−l+1)^2。
CPP
        if(l==n&&r==1){  
            lastans=0;
        }else{
            lastans=(r-l+1)*(r-l+1);
        }
        cout<<lastans<<endl;

AC CODE

CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...