【题目来源】
洛谷：P1116 车厢重组 - 洛谷 (luogu.com.cn)
【题目描述】
在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转 \(180\) 度，则可以把相邻两节车厢的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后，火车站决定将这一工作自动化，其中一项重要的工作是编一个程序，输入初始的车厢顺序，计算最少用多少步就能将车厢排序。
【输入】
共两行。
第一行是车厢总数 \(N(\le 10000)\)。
第二行是 \(N\) 个不同的数表示初始的车厢顺序。
（注：实际上数据中并不都在同一行，有可能分行输入）
【输出】
一个整数，最少的旋转次数。
【输入样例】
4
4 3 2 1
【输出样例】
6
【解题思路】
【算法标签】
《洛谷 P1116 车厢重组》 #模拟# #排序#
【代码详解】
#include <bits/stdc++.h>
using namespace std;int main() {int n, a[10005], ans = 0; // n: 数组长度，a: 存储数组，ans: 记录交换次数cin >> n; // 输入数组长度for (int i = 1; i <= n; i++) cin >> a[i]; // 输入数组元素// 冒泡排序，并统计交换次数for (int i = n; i >= 1; i--) { // 外层循环，控制排序范围for (int j = 1; j < i; j++) { // 内层循环，比较相邻元素if (a[j] > a[j + 1]) { // 如果前一个元素大于后一个元素swap(a[j], a[j + 1]); // 交换两个元素ans++; // 交换次数加1}}}// 输出交换次数cout << ans;return 0;
}
【运行结果】
4
4 3 2 1
6