自动搬运

查看原文

来自洛谷，原作者为

	dutianchen1 EL PSY KONGROO

搬运于2025-08-24 22:46:50，当前版本为作者最后更新于2024-10-10 20:16:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[PA 2022] Fotografia

题意概括

给一个序列 $a$。有无数次操作，每次操作可以选取 $p_{1},p_{2},\dots p_{n}$，让 $a_{p_{i}} \gets a_{p_{n-i+1}}$。我们要让原序列升序排列，求最少操作次数。

思路简析

对题意分析，我们可以知道：对序列排序后，整个序列其实是由一个个环组成，每个环都是由要相互交换的元素组成，而我们的目的就是让原序列形成一个个自环。

用样例 $1$ 说明一下：

原序列（转化为序号后）：$4,5,3,1,2$，我们的目标：$1,2,3,4,5$。

这个样例中 $1$ 和 $4$ 形成了一个环，$2$ 和 $5$ 形成了一个环。

而我们每次的操作本质就是破环或合并环。

贪心考虑，我们不会合并环，于是考虑如何拆环最优。

显然，当环由两个元素组成时，直接拆分便可。

当环长 $\ge 3$ 时，我们可以发现，一次操作必然能把一个大环拆成若干个环长 $\le2$，再进行一次操作就可以把所有环长为 $2$ 的环都拆分成自环。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+5;
inline ll read()
{
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}
	return x*f;
}
struct node{
	ll val,id;
}num[N];
bool cmp(node a,node b){
	return a.val<b.val;
}
ll opt[N];
ll n,top;
bool vis[N];
ll c[N];//记录环 
vector<vector<ll>> ans;
int main(){
	n=read();
	for(int i=1;i<=n;i++){
		num[i].val=read();num[i].id=i;
	}
	sort(num+1,num+1+n,cmp);
	for(int i=1;i<=n;i++)opt[num[i].id]=i;//记录环 
	while(true){
		vector<ll> a,b;
		memset(vis,false,sizeof(vis));
		for(int i=1;i<=n;i++){//跑环 
			if(vis[i])continue;
			top=0;
			ll x=i;
			while(!vis[x]){
				c[++top]=x;
				vis[x]=true;
				x=opt[x];
			} 
			ll l=1,r=top;
			while(l<r){
				swap(opt[c[l]],opt[c[r]]);
				a.push_back(c[l]);
				b.push_back(c[r]);
				l++;r--;
			}
		}
		reverse(a.begin(),a.end());
		a.insert(a.end(),b.begin(),b.end());
		if(a.empty())break;
		ans.push_back(a);
	} 
	cout<<ans.size()<<'\n';
	for(int i=0;i<ans.size();i++){
		cout<<ans[i].size()<<'\n';
		for(int j=0;j<ans[i].size();j++){
			cout<<ans[i][j]<<' ';
		}cout<<'\n';
	}
    return 0;  
}