csp信奥赛C++高频考点专项训练：【排序算法】案例3：车厢重组

csp信奥赛C高频考点专项训练【排序算法】案例3车厢重组题目描述在一个旧式的火车站旁边有一座桥其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢如果将桥旋转180 180180度则可以把相邻两节车厢的位置交换用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后火车站决定将这一工作自动化其中一项重要的工作是编一个程序输入初始的车厢顺序计算最少用多少步就能将车厢排序。输入格式共两行。第一行是车厢总数N ( ≤ 10000 ) N( \le 10000)N(≤10000)。第二行是N NN个不同的数表示初始的车厢顺序。注实际上数据中并不都在同一行有可能分行输入输出格式一个整数最少的旋转次数。输入输出样例 #1输入 #14 4 3 2 1输出 #16AC代码#includebits/stdc.husingnamespacestd;intn,a[10010],cnt0;// n: 车厢总数, a: 存储车厢顺序的数组, cnt: 记录交换次数intmain(){// 读入车厢总数cinn;// 读入初始的车厢顺序for(inti1;in;i){cina[i];}// 冒泡排序算法for(inti1;in-1;i){// 外层循环控制排序轮数共需要n-1轮for(intj1;jn-i;j){// 内层循环每轮比较相邻元素if(a[j]a[j1]){// 如果前一个车厢号大于后一个车厢号swap(a[j],a[j1]);// 交换两个车厢的位置cnt;// 交换次数加1}}}// 输出最少的旋转次数即交换次数coutcnt;return0;}功能分析算法原理这段代码使用冒泡排序算法来解决车厢重组问题问题转化将车厢排序问题转化为冒泡排序中的相邻元素交换问题核心思想通过相邻车厢的多次交换最终使所有车厢按编号从小到大排列计数原理每次交换对应题目中的一次旋转操作关键点说明cnt变量准确记录了题目要求的最少旋转次数冒泡排序的交换次数正好等于将逆序序列变为顺序序列所需的最少相邻交换次数对于示例输入4 3 2 1需要6次交换才能变成1 2 3 4完整信奥赛C普及组CSP-J一等奖通关刷题题单及题解请关注专栏https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}