Codeforces Round #252 (Div. 2) D

http://codeforces.com/problemset/problem/441/D

置换群的基本问题，一个轮换内交换成正常顺序需要k-1次，k为轮换内元素个数

两个轮换之间交换元素，可以把两个轮换合并成1个，总交换次数+1

一个轮换内部交换，可以把一个轮换拆分成两个，总交换次数-1

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

using namespace std ;

int n,m ;

int nxt[],vis[] ;

vector <pair<int,int> > ans ;

int cal()

{

    memset(vis,,sizeof(vis)) ;

    int st= ;

    int cnt= ;

    for(int i= ;i<=n ;i++)

        if(!vis[i])

        {

            vis[i]=st++ ;

            int res= ;

            for(int j=nxt[i] ;!vis[j] ;j=nxt[j])

            {

                vis[j]=vis[i] ;

                res++ ;

            }

            cnt+=(res-) ;

        }

    return cnt ;

}

int main()

{

    scanf("%d",&n) ;

    for(int i= ;i<=n ;i++)

        scanf("%d",&nxt[i]) ;

    scanf("%d",&m) ;

    while()

    {

        int ret=cal() ;

        if(ret==m)break ;

        if(ret<m)//两个轮换换，可以把两个轮换合并成1个，ret+1 ，保证字典序最小，所以和位置1换

        {

            for(int i= ;i<=n ;i++)

                if(vis[i]!=vis[])

                {

                    swap(nxt[],nxt[i]) ;

                    ans.push_back(make_pair(,i)) ;

                    break ;

                }

        }

        else//一个轮换内换，可以把一个轮换拆成两个，ret-1

        {

            int i,j ;

            for(i= ;i<=n ;i++)

                if(nxt[i]!=i)break ;

            for(int j=i+ ;j<=n ;j++)

                if(vis[j]==vis[i])

                {

                    swap(nxt[i],nxt[j]) ;

                    ans.push_back(make_pair(i,j)) ;

                    break ;

                }

        }

    }

    printf("%d\n",ans.size()) ;

    for(int i= ;i<ans.size() ;i++)

        printf("%d %d ",ans[i].first,ans[i].second) ;

    return  ;

}