藍橋杯第七屆B組第九題 交換瓶子（選擇排序）

題目在這個OJ上可以送出：http://simpleoj.cn/index.php/home/problem/pro_info/id/86.html

交換瓶子

有N個瓶子，編号 1 ~ N，放在架子上。

比如有5個瓶子：

2 1 3 5 4

要求每次拿起2個瓶子，交換它們的位置。

經過若幹次後，使得瓶子的序号為：

1 2 3 4 5

對于這麼簡單的情況，顯然，至少需要交換2次就可以複位。

如果瓶子更多呢？你可以通過程式設計來解決。

輸入格式為兩行：

第一行: 一個正整數N（N<10000）, 表示瓶子的數目

第二行：N個正整數，用空格分開，表示瓶子目前的排列情況。

輸出資料為一行一個正整數，表示至少交換多少次，才能完成排序。

例如，輸入：

5

3 1 2 5 4

程式應該輸出：

3

再例如，輸入：

5

5 4 3 2 1

程式應該輸出：

2

資源約定：

峰值記憶體消耗 < 256M

CPU消耗 < 1000ms

請嚴格按要求輸出，不要畫蛇添足地列印類似：“請您輸入…” 的多餘内容。

所有代碼放在同一個源檔案中，調試通過後，拷貝送出該源碼。

注意: main函數需要傳回0

注意: 隻使用ANSI C/ANSI C++ 标準，不要調用依賴于編譯環境或作業系統的特殊函數。

注意: 所有依賴的函數必須明确地在源檔案中 #include ， 不能通過工程設定而省略常用頭檔案。

送出時，注意選擇所期望的編譯器類型。

【思路分析】首先把這些東西排好序，而且要交換的次數最少，那麼非選擇排序不可，因為選擇排序是每次在剩餘的所有數中尋找一個最小的放在最先面，這樣的話可以保證交換次數最少。而且這個題的這n個瓶子大小是從1到n，那麼我們可以用”桶“的的形式來記錄大小為i的瓶子的位置所在，然後再進行交換就簡單了。

【AC代碼】

#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;
#define LL long long
#define PI acos(-1.0)

int a[],book[];//book[i]記錄的大小為i的瓶子的位置

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(int i=; i<=n; i++)
        {
            scanf("%d",&a[i]);//大小為a[i]的瓶子的位置為i
            book[a[i]]=i;
        }
        int sum=;
        for(int i=; i<=n; i++)
        {
            if(i!=a[i])//第i個位置放置的一定是大小為i的瓶子，這裡采用的是選擇排序的思想
            {
                sum++;
                int x=book[i];//第i個瓶子的位置
                int temp=a[x];
                a[x]=a[i];
                book[a[i]]=x;
                a[i]=temp;
                book[i]=i;
            }
        }
        printf("%d\n",sum);
    }
    return ;
}