P8637（洛谷题面）

题目

题目描述：

有 NN 个瓶子，编号 1∼N1 \sim N，放在架子上。

比如有 55 个瓶子：

2,1,3,5,42,1,3,5,4

要求每次拿起 22 个瓶子，交换它们的位置。

经过若干次后，使得瓶子的序号为：

1,2,3,4,51,2,3,4,5

对于这么简单的情况，显然，至少需要交换 22 次就可以复位。

如果瓶子更多呢？你可以通过编程来解决。

输入格式：

第一行：一个正整数 NN（N<10000N<10000），表示瓶子的数目。

第二行：NN 个正整数，用空格分开，表示瓶子目前的排列情况。

输出格式：

输出数据为一行一个正整数，表示至少交换多少次，才能完成排序。

数据范围与说明：

时限 1 秒, 256M。蓝桥杯 2016 年第七届省赛

蓝桥杯 2016 年省赛 B 组 I 题。

输入输出样例 #1

输入：

1
2
5
3 1 2 5 4

输出：

1
3

输入输出样例 #2

输入：

1
2
5
5 4 3 2 1

输出：

1
2

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
int main(){
    int arr[10001];
    int n,count=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&arr[i]);
    } 
    for(int i=1;i<=n;i++){
        if(arr[i]!=i){
            for(int j=1;j<=n;j++){
                if(arr[j]==i){
                    swap(arr[j],arr[i]);
                    count++;
                }
            }
        }
    }
    printf("%d ",count);
}