P8637 [蓝桥杯 2016 省 B] 交换瓶子 - 洛谷

题目描述

有 N 个瓶子，编号 1∼N，放在架子上。

比如有 5 个瓶子：

markdow

2, 1, 3, 5, 4

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

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

markdown

1, 2, 3, 4, 5

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

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

输入格式

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

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

输出格式

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

输入输出样例

输入 #1

markdown

5
3 1 2 5 4

输出 #1

markdown

3

输入 #2

markdown

5
5 4 3 2 1

输出 #2

markdown

2

说明/提示

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

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

思路：

直接模拟从第一个到最后一个，是否与正确的答案相同，不是就翻转i和i+1

代码如下：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 1e5+10;
int a[N],n,cnt;
int main() 
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;for(int i = 1 ; i <= n ; i++){cin >> a[i];}for(int i = 1 ; i <= n ; i++){if(a[i] != i){for(int j = i ; j <= n ; j++){if(a[j] == i){swap(a[i],a[j]);cnt++;}}}}cout << cnt;return 0;
}