武进附近做网站的公司有哪些,简述设计优秀电子商务网站的成功要素,建设银行网网站,加强网站内容建设的意见题目描述
在一个旧式的火车站旁边有一座桥#xff0c;其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢#xff0c;如果将桥旋转 180 180 180 度#xff0c;则可以把相邻两节车厢的位置交换#xff0c;用这种方法可以重新排列车厢的顺序…题目描述
在一个旧式的火车站旁边有一座桥其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢如果将桥旋转 180 180 180 度则可以把相邻两节车厢的位置交换用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后火车站决定将这一工作自动化其中一项重要的工作是编一个程序输入初始的车厢顺序计算最少用多少步就能将车厢排序。
输入格式
共两行。
第一行是车厢总数 N ( ≤ 10000 ) N( \le 10000) N(≤10000)。
第二行是 N N N 个不同的数表示初始的车厢顺序。 注实际上数据中并不都在同一行有可能分行输入
输出格式
一个整数最少的旋转次数。
样例 #1
样例输入 #1
4
4 3 2 1样例输出 #1
61.题目分析
输入车厢节数对应的车厢序号将车厢序号从小到大进行排序。 限制只能在相邻车厢之间交换位置求最小交换次数。
这里很容易想到冒泡排序即通过相邻元素之间的变换对元素进行排序。附上之间写的冒泡排序的详解 冒泡排序。
2.题目思路
键入车厢节数车厢序号。将序号存入数组。将数组进行冒泡排序记录每一轮交换元素的次数。最后打印总共次数即可。
3.代码实现
#include iostreamusing 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;
}
