codeforces 489A.SwapSort 解题报告

题目链接：http://codeforces.com/problemset/problem/489/A

题目意思：给出一个 n 个无序的序列，问能通过两两交换，需要多少次使得整个序列最终呈现非递减形式。这个交换次数最多为 n 次。如果原来已经非递减排列好，输出次数为0；否则不但要输出次数，还需要输出每次交换的数组下标。

　　比赛的时候想复杂了，用了pair来记录值和坐标，还要开多一个pair类型的 b 数组来保存已排好序的序列，然后跟原序列比较......哪个复杂啊～～～然后校园网12：00 断网了，比原来提早半小时 = =，不过都好，原来的做法是错的。

    其实之所以没有向简单的方法想，是因为被最多 n 次这个条件吓到了，没有仔细想清楚，以为两两比较最终会超 n 次。其实是不会的。

　　遍历 0 ～ n-1 的位置，选出最小，然后次小，第三小，.....，直到最大。如果发现当前位置放置的数是正确的，就continue，最多最多交换次数是 O(n) ！

    15ms 版本

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 3000 + 10;
int a[maxn];
int res[maxn][2];

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
    #endif
    int n;

    while (scanf("%d", &n) != EOF)
    {
        for (int i = 0; i < n; i++)
            scanf("%d", &a[i]);
        int cnt = 0;
        for (int i = 0; i < n; i++)
        {
            int minn = a[i];
            int choice = i;
            for (int j = i+1; j < n; j++)
            {
                if (a[j] < minn)
                {
                    minn = a[j];
                    choice = j;
                }
            }
            if (choice == i)
                continue;
            res[cnt][0] = i;
            res[cnt++][1] = choice;
            swap(a[i], a[choice]);
        }
        printf("%d
", cnt);
        for (int i = 0; i < cnt; i++)
            printf("%d %d
", res[i][0], res[i][1]);
    }
    return 0;
}

   至于下面这个呢，是参考乌冬子写的，用到 STL 中的 min_element(first, end, cmp)，其中cmp为可选择参数！

表示在[first, end) （看清楚，这个是左闭右开区间）中查找最小的元素。max_element则是查找最大元素。

　 这个函数我也是第一次见，*min_element(first, end, cmp)代表这个最小的元素的值。

   假设数组用a[]来表示。min_element(a[i], a[i]+n) - a  才返回最小元素的值的下标！！！

　 乌冬子的做法还有一个巧妙的地方，就是即使元素放置位置正确，也原地输出交换下标，即类似输出 i i 这种。而且还有一点就是不需要开多一个数组来存储答案。真应该给个大大的赞他呀～～～～^_^，有一个稍稍瑕疵就是时间用多了，需要 31ms ！STL 普遍都是这样的。

　 31ms 偷师版   

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 3000 + 10;
int a[maxn];

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
    #endif
    int n;

    while (scanf("%d", &n) != EOF)
    {
        for (int i = 0; i < n; i++)
            scanf("%d", &a[i]);
        printf("%d
", n);
        for (int i = 0; i < n; i++)
        {
            int j = min_element(a+i, a+n) - a;
            printf("%d %d
", i, j);
            swap(a[i], a[j]);
        }
    }
    return 0;
}