洛谷刷题题解-P1047[NOIP2005普及组]车厢重组

洛谷刷题题解-P1047[NOIP2005普及组]车厢重组

首先，我们来看一下题目要求

如图

我认为做题首先要快速抽象出题目的数学模型。本题的数学模型是输入一个数组，在只能交换相邻元素的条件下对其进行排序。

遇到的问题1：怎样使交换次数最少？

冒泡法排序是交换相邻元素交换次数最少的方法，至于为什么？我不知道。。。

遇到的问题2：注意边界问题

冒泡法排序中如果你使用a[i]与a[i+1]进行比较 ，要注意两重循环的循环变量都小于n-1/n

遇到的问题3：数组要设置大一些，以防测试数据较大，有些变量要初始化

题解如图