题目描述
有 N 个瓶子,编号 1∼N,放在架子上。
比如有 5 个瓶子:
2 1 3 5 4
要求每次拿起 2 个瓶子,交换它们的位置。
经过若干次后,使得瓶子的序号为:
1 2 3 4 5
对于这么简单的情况,显然,至少需要交换 2 次就可以复位。
如果瓶子更多呢?
样例
input:
5
3 1 2 5 4
output:
3
C++ 代码(贪心)
#include <iostream>
using namespace std;
const int N = 10010;
int n, a[N], ans;
int main(void){
scanf("%d", &n);
for(int i = 1; i <= n; i ++)
scanf("%d", &a[i]);
// flag 判别是否已经按照1-N的顺序排列
bool flag;
do{
flag = true;
for(int i = 1; i <= n; i ++)
if(i != a[i])
// 贪心:一旦第i个位置上的数不是i,而是任意非i数x
// 则此时x位置上的数比不为x, 交换a[i]与a[x],使得 a[x] 存放 x
flag = false, swap(a[i], a[a[i]]), ans ++;
}while(! flag);
printf("%d\n", ans);
return 0;
}