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

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

有 N 个瓶子，编号 1∼N，放在架子上。
好比有 5 个瓶子：
markdow

1. 2, 1, 3, 5, 4

复制代码

要求每次拿起 2 个瓶子，交换它们的位置。
颠末若干次后，使得瓶子的序号为：
markdown

1. 1, 2, 3, 4, 5

复制代码

对于这么简单的情况，显然，至少需要交换 2 次就可以复位。
如果瓶子更多呢？你可以通过编程来解决。
输入格式

第一行：一个正整数 N（N<10000），表示瓶子的数目。
第二行：N 个正整数，用空格分开，表示瓶子目前的排列情况。
输出格式

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

输入 #1
markdown

1. 5
2. 3 1 2 5 4

复制代码

输出 #1
markdown

1. 3

复制代码

输入 #2
markdown

1. 5
2. 5 4 3 2 1

复制代码

输出 #2
markdown

1. 2

复制代码

分析/提示

时限 1 秒，256M。蓝桥杯 2016 年第七届省赛
蓝桥杯 2016 年省赛 B 组 I 题。
思路：
直接模拟从第一个到最后一个，是否与精确的答案相同，不是就翻转i和i+1

代码如下：

1. #include<iostream>
2. #include<algorithm>
3. #include<vector>
4. using namespace std;
5. const int N = 1e5+10;
6. int a[N],n,cnt;
7. int main()
8. {
9.         ios::sync_with_stdio(0);
10.         cin.tie(0);
11.         cout.tie(0);
12.         cin >> n;
13.         for(int i = 1 ; i <= n ; i++)
14.         {
15.                 cin >> a[i];
16.         }
17.         for(int i = 1 ; i <= n ; i++)
18.         {
19.                 if(a[i] != i)
20.                 {
21.                         for(int j = i ; j <= n ; j++)
22.                         {
23.                                 if(a[j] == i)
24.                                 {
25.                                         swap(a[i],a[j]);
26.                                         cnt++;
27.                                 }
28.                         }
29.                 }
30.         }
31.         cout << cnt;
32.         return 0;
33. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。