交換瓶子

原題目鏈接

題目描述

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

例如有 5 個瓶子，當前排列為：

2 1 3 5 4

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

要求通過若干次交換，使得瓶子的編號從小到大排列為：

1 2 3 4 5

對于簡單情況，顯然至少需要交換 2 次就能復位。

如果瓶子更多呢？請你編程解決這個問題，找出最少交換次數。

---

輸入描述

輸入格式為兩行：

• 第一行：一個正整數 N (N < 10?)，表示瓶子的數目；
• 第二行：N 個正整數，空格分隔，表示當前瓶子的排列情況。

---

輸出描述

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

---

輸入輸出樣例

示例

輸入

5
3 1 2 5 4

輸出

3

c++代碼

#include<bits/stdc++.h>using namespace std;int N, ans = 0;int main() {cin >> N;vector<int> root(N);for (int i = 0; i < N; i++) cin >> root[i];for (int i = 0; i < N; i++) {while(root[i] != i + 1) {swap(root[i], root[root[i] - 1]);ans++;}}cout << ans;return 0;
}//by wqs

題目解析

貪心算法

我們假設當前的值不對應

說明我們一定要交換

我們要交換次數最小，就要這次交換的利益最大。

如果我們交換一次剛好和可以讓兩個數同時對應，這樣利益最大，貪心的做法也就是和對應值交換

為什么呢，因為這樣既可以保證至少有一個可以對應，還有機會可以對應兩個。

例如

3 1 2 5 4

1 2 3 4 5

3和1不同，第一個和第三個交換，至少3對應了。

2 1 3 5 4

1 2 3 4 5

2 1 不同，第二個和第一個交換,1和2都對應了。

1 2 3 5 4

1 2 3 4 5