题解：P9259 [PA 2022] Fotografia

· · 题解

[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;  
}