目录
?题目描述:
乍一看:不就是冒泡
那么转换问题:用逆序数代替最小步数
问题转换:归并排序是什么?怎么在归并排序中计数?
最后吐槽一波。
?题目描述:
Description
小张在暑假时间来到工地搬砖挣钱。包工头交给他一项艰巨的任务,将一排砖头按照从低到高的顺序排好。可是小张的力量有限,每次只能交换相邻的两块砖头,请问他最少交换几次能够完成任务?
Input
第一行一个整数 n(1 - 300000 ) ,表示砖头数量。
第二行 n 个整数 (-1000000000-1000000000 ) ,表示砖头的高度。
Output
一个整数,表示最少交换几次能够完成任务。
乍一看:不就是冒泡
你要知道,交换,排序,最少步数。
第一个会想到冒泡,但是时间复杂度是n^2,所以一定会超时。
那么转换问题:用逆序数代替最小步数
https://blog.csdn.net/ojshilu/article/details/17066737
?把最小步数转换成求逆序数,但是其实本质还是冒泡排序,看完上面那篇文章你就理解了,或者直接用即可。
关键是,转换成求逆序数,你就可以在csdn上找出一大堆教程,常用的是归并排序求逆序数,至于用树状数组求,是高级玩法了,咱这种上csdn找题解的,就别掺和了,如果有时间,学一学倒是也不错,以后迟早要学树状数组的。
问题转换:归并排序是什么?怎么在归并排序中计数?
https://blog.csdn.net/qq_35344198/article/details/106857042
这篇图画的好,也有实例,便于理解思想,然而不是c语言
https://blog.csdn.net/weixin_46726346/article/details/105913203?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522163066218016780357269849%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=163066218016780357269849&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-105913203.first_rank_v2_pc_rank_v29&utm_term=%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8Fc%E8%AF%AD%E8%A8%80&spm=1018.2226.3001.4187
这篇是c语言,而且讲的也比较详细,但是他用的递归,递归一方面是速度会拖慢,我之前用斐波那契数列,和这个都是双递归,开到50个左右递归,就已经跑不动了;另一方面递归一层一层地理解起来稍微难一点;还有就是他代码写的稍微有点啰嗦。
实际上有非递归的方式。
https://blog.csdn.net/qq_38701476/article/details/81712562?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522163066592416780271568817%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=163066592416780271568817&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-81712562.first_rank_v2_pc_rank_v29&utm_term=%E6%B1%82%E9%80%86%E5%BA%8F%E6%95%B0&spm=1018.2226.3001.4187
最终解答,这篇是c++,不过只用到个>>符号,你就把他当自动规定类型的scanf和printf好了
这篇还讲了树状数组,不过我是没时间研究了,等以后有题非用这算法不可,我才学
不得不提的是,这个人后面还装起来了,/2就除2,还用个>>1位运算装逼,我yue~
最后吐槽一波。
真的不要随便用单个字母当变量名,那个l和1太像了,关键是变量名含义不够清晰,不是一个好习惯。
|