(Codeforces) 441D. Valera and Swaps

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

題目大意：給你一個permutation P，設f(P)代表把P變成1,2,3, ... , n-1, n的最小次數。現在指定要使得f(P) = q，請問最少要move多少次，請把過程輸出，並使用字典序最小的解！

先有一個permutation的感覺，假設在P這個全排列中第i個位置的值是p[i]，則我們如果把所有的i-->p[i]建圖，那我們會得到一些環(cycle)，那，把p變成1,2,3, ...... , n-1, n的最小次數就是n-cycle的數量！(可以簡單畫圖試試看喔！)。

知道這個結論之後，我們就可以分成兩種case：一種是f(P)太多(現在的cycle太少)，另外一種是f(P)太少(現在的cycle太多)

對於第二種case，我們要讓cycle變少，又要是字典序最小的話，可以很greedy的一直跟拿跟i=1不同的cycle中，i最小的跟1換，只要有交換的動作，不是會把兩個cycle merge再一起，就是會把一個cycle 給split成兩個cycle。這樣的複雜度是O(N)

對於第一種case：我們可以每找到一個在同一個cycle最小的兩個id後，把圖砍掉重建，這樣的複雜度是O(N^2)

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cstring>
#include <utility>
#include <algorithm>
using namespace std;

typedef pair<int,int> pii;
const int MAX_N = 3e3 + 6;

int a[MAX_N];
bool visit[MAX_N];
vector<int> ala[MAX_N];

int main () {
    int n;
    while (scanf("%d",&n) != EOF) {
        for (int i=0;n>=i;i++) {
            ala[i].clear();
        }
        for (int i=1;n>=i;i++) {
            int x;
            scanf("%d",&x);
            a[i]=x;
        }
        memset(visit,0,sizeof(visit));
        int _;
        scanf("%d",&_);
        int sz=0;
        for (int i=1;n>=i;i++) {
            if (!visit[i]) {
                sz++;
                int __=i;
                while (!visit[__]) {
                    visit[__]=1;
                    ala[sz].push_back(__);
                    __ = a[__];
                }
            }
        }
        if (n-sz == _) {
            puts("0");
            continue;
        }
        else if (n-sz >= _) {
            vector<pii> ans;
            //too much
            int need=(n-sz-_);
            printf("%d\n",(n-sz-_));
            while (need--) {
                pii alala=make_pair(n+1,n+1);
                int mn1=n+1,mnid=n+1;
                for (int i=1;sz>=i;i++) {
                    if (ala[i].size()!=1) {
                        int len=ala[i].size();
                        for (int j=0;len>j;j++) {
                            if (ala[i][j] < mn1) {
                                mn1=ala[i][j];
                                mnid=i;
                            }
                        }
                    }
                }
                int mn2=n+1;
                for (int i=1;sz>=i;i++) {
                    if (i!=mnid) continue;
                    if (ala[i].size()!=1) {
                        int len=ala[i].size();
                        for (int j=0;len>j;j++) {
                            if (ala[i][j] < mn2 && ala[i][j] != mn1) {
                                mn2=ala[i][j];
                                mnid=i;
                            }
                        }
                    }
                }
                alala = make_pair(mn1,mn2);
                printf("%d %d ",alala.first,alala.second);
                swap(a[alala.first],a[alala.second]);
                memset(visit,0,sizeof(visit));
                sz=0;
                for (int i=1;n>=i;i++) {
                    ala[i].clear();
                }
                for (int i=1;n>=i;i++) {
                    if (!visit[i]) {
                        sz++;
                        int __=i;
                        while (!visit[__]) {
                            visit[__]=1;
                            ala[sz].push_back(__);
                            __ = a[__];
                        }
                    }
                }
            }
            puts("");
        }
        else if (n-sz < _){
            vector<pii> ans;
            //too few
            int need = _-(n-sz);
            for (int i=2;sz>=i;i++) {
                ans.push_back(make_pair(ala[1][0],ala[i][0]));
            }
            sort(ans.begin(),ans.end());
            printf("%d\n",-(n-sz-_));
            for (auto i:ans) {
                printf("%d %d ",i.first,i.second);
                need--;
                if (!need) break;
            }
            puts("");
        }
    }
}