CodeForces

A permutation p of length n is a sequence of distinct integers p1, p2, ..., pn (1 ≤ pi ≤ n). A permutation is an identity permutation, if for any i the following equation holds pi = i.

A swap (i, j) is the operation that swaps elements pi and pj in the permutation. Let's assume that f(p) is the minimum number of swaps that you need to make the permutation p an identity permutation.

Valera wonders, how he can transform permutation p into any permutation q, such that f(q) = m, using the minimum number of swaps. Help him do that.


Input

The first line contains integer n (1 ≤ n ≤ 3000) — the length of permutation p. The second line contains n distinct integers p1, p2, ..., pn (1 ≤ pi ≤ n) — Valera's initial permutation. The last line contains integer m (0 ≤ m < n).

Output

In the first line, print integer k — the minimum number of swaps.

In the second line, print 2k integers x1, x2, ..., x2k — the description of the swap sequence. The printed numbers show that you need to consecutively make swaps (x1, x2), (x3, x4), ..., (x2k - 1, x2k).

If there are multiple sequence swaps of the minimum length, print the lexicographically minimum one.

Examples
Input
5
1 2 3 4 5
2
Output
2
1 2 1 3
Input
5
2 1 4 5 3
2
Output
1
1 2
Note

Sequence x1, x2, ..., xs is lexicographically smaller than sequence y1, y2, ..., ys, if there is such integer r (1 ≤ r ≤ s), that x1 = y1, x2 = y2, ..., xr - 1 = yr - 1 and xr < yr.

题意:有函数f(p),表示把排列p,变为顺序的排列,所用的最小交换次数,这里的交换是两两交换,而不是相邻交换。

          现在给你排列p和m,让你交换最小的次数,使得排列变为q,满足f(q)=m,如果有多种交换方案,输出字典序最小的;

思路:1,把排列p变为1,2,3....p,的最小次数=N-环数。假如N-环数<m,那就加环。 否则减环。

           2,如果交换两个不在同一个环的位置的数,那么环数+1;

           3,如果交换在同一个环的位置的数,那么环数-1;

所以我们的任务就是加环或者减环,而每次分组的复杂度是O(N);我们最多加N次环,所以我们可以暴力交换,交换后重新分组。

复杂度O(N^2);

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=3010;
int a[maxn],vis[maxn],tot,N,M;
void dfs(int u)
{
    if(vis[u]) return ;
    vis[u]=tot;
    dfs(a[u]);
}
void rebuild()
{
    tot=0; rep(i,1,N) vis[i]=0;
    rep(i,1,N) if(!vis[i]) tot++,dfs(i);
}
int main()
{
    scanf("%d",&N);
    rep(i,1,N) scanf("%d",&a[i]);
    rebuild();
    scanf("%d",&M);
    if(M==N-tot) return puts("0"),0;
    int ans,opt=0;
    if(M>N-tot) ans=M-N+tot,opt=1; //
    else ans=N-tot-M;//
    printf("%d
",ans);
    rep(i,1,N)
     rep(j,1,N){
        if(!ans) break;
        if(i!=j&&(abs(vis[i]-vis[j])?1:0)==opt) {
            swap(a[i],a[j]); ans--;
            printf("%d %d ",i,j);
            rebuild();
        }
    }
    return 0;
}
原文地址:https://www.cnblogs.com/hua-dong/p/10427461.html