IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 【第十二题】排队/搬砖(北理工/北京理工大学/程序设计方法与实践/小学期 )(无源码) -> 正文阅读

[数据结构与算法]【第十二题】排队/搬砖(北理工/北京理工大学/程序设计方法与实践/小学期 )(无源码)

目录

?题目描述:

乍一看:不就是冒泡

那么转换问题:用逆序数代替最小步数

问题转换:归并排序是什么?怎么在归并排序中计数?

最后吐槽一波。


?题目描述:

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太像了,关键是变量名含义不够清晰,不是一个好习惯。

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-09-04 17:47:48  更:2021-09-04 17:50:05 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 1:31:36-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码