題目描述
有N個瓶子，編號 1 ~ N，放在架子上。
比如有5個瓶子：
2 1 3 5 4
要求每次拿起2個瓶子，交換它們的位置。
經(jīng)過若干次后，使得瓶子的序號為：
1 2 3 4 5
對于這么簡單的情況，顯然，至少需要交換2次就可以復(fù)位。
如果瓶子更多呢？你可以通過編程來解決。
輸入輸出
輸入格式為兩行：
第一行: 一個正整數(shù)N（N<10000）, 表示瓶子的數(shù)目
第二行：N個正整數(shù)，用空格分開，表示瓶子目前的排列情況。
輸出數(shù)據(jù)為一行一個正整數(shù)，表示至少交換多少次，才能完成排序。
例如，輸入：
5
3 1 2 5 4
程序應(yīng)該輸出：
3
再例如，輸入：
5
5 4 3 2 1
程序應(yīng)該輸出：
2
資源約定
峰值內(nèi)存消耗 < 256M
CPU消耗 < 3000ms
思路
這題思路很巧妙，我們可以將其轉(zhuǎn)化為圖論的問題求解。
首先建圖，因為是1~N的，所以將a[i]指向a[a[i]]，例如第一個樣例。文章來源：http://www.zghlxwxcb.cn/news/detail-836623.html
5
3 1 2 5 4
轉(zhuǎn)化成圖就行如下所示。
排好之后的圖是這樣的。
所以我們的目的就是將上面的兩個環(huán)，變成下面的五個環(huán)。每次交換兩個點，其實就是改變了兩條邊的指向。比如交換3和2，就變成了2 1 3 5 4。新圖就變成了：
其實就是將一個環(huán)變成了兩個環(huán)。每一次這樣的交換都會導致上述結(jié)果。那么我們最終是要有
n
n
n 個環(huán)。所以我們只需要求出給出的數(shù)據(jù)有多少環(huán)，然后讓
n
n
n 減去環(huán)的數(shù)量，就是最少的交換次數(shù)。文章來源地址http://www.zghlxwxcb.cn/news/detail-836623.html
代碼
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10010;
int n;
int a[N];
bool st[N];
int main()
{
cin >> n;
for ( int i = 1; i <= n; i ++ ) cin >> a[i];
int k = 0;
for ( int i = 1; i <= n; i ++ )
if ( !st[i] )
{
k ++;
for ( int j = i; !st[j]; j = a[j] )
st[j] = true;
}
cout << n - k << endl;
return 0;
}
到了這里，關(guān)于交換瓶子【第七屆】【省賽】【A組】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
