P1116 车厢重组（冒泡排序）

题目描述

在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转 $180$ 度，则可以把相邻两节车厢的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后，火车站决定将这一工作自动化，其中一项重要的工作是编一个程序，输入初始的车厢顺序，计算最少用多少步就能将车厢排序。

输入格式

共两行。

第一行是车厢总数 $N(\le 10000)$。

第二行是 $N$ 个不同的数表示初始的车厢顺序。
（注：实际上数据中并不都在同一行，有可能分行输入）

输出格式

一个整数，最少的旋转次数。

样例 #1

样例输入 #1

4
4 3 2 1

样例输出 #1

6

1.题目分析

输入车厢节数，对应的车厢序号，将车厢序号从小到大进行排序。
限制只能在相邻车厢之间交换位置，求最小交换次数。

这里很容易想到冒泡排序：即通过相邻元素之间的变换，对元素进行排序。附上之间写的冒泡排序的详解： 冒泡排序。

2.题目思路

1. 键入车厢节数，车厢序号。
2. 将序号存入数组。
3. 将数组进行冒泡排序，记录每一轮交换元素的次数。
4. 最后打印总共次数即可。

3.代码实现

#include <iostream>using namespace std;int main() {int n;//输入车厢节数cin >> n;int arr[n];for (int i = 0; i < n; ++i) {cin >> arr[i];}int temp;//记录冒泡的次数int cnt = 0;//冒泡排序for (int i = 0; i < n - 1; ++i) {for (int j = 0; j < n - i - 1; ++j) {if (arr[j] > arr[j + 1]) {temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;cnt++;}}}//打印结果cout << cnt;return 0;
}