USACO analysis
肖肖 |
26 Nov 2020
报告错误
如果你发现该网页中存在错误/显示异常，可以从以下两种方式向我们报告错误，我们会尽快修复：
- 使用 CS Club 网站错误 为主题，附上错误截图或描述及网址后发送邮件到 286988023@qq.com
- 在我们的网站代码仓库中创建一个 issue 并在 issue 中描述问题 点击链接前往Github仓库
⚠ 该解析描述需要进一步细化和具体实现
我们认为这条解析不够完善，如果你有更好的解析/更加详细的思路欢迎用微信发给mark或者以"USACO Solution"为主题发送到 286988023@qq.com题目
给出一个长度为N的乱序数组,每次只能将首位移动到后面的某一个位置,要求求出将数组变为升序的最小步骤和每次移动长度
分析
我们可以将数组分成两个部分,前面一个部分使无序的数组,而后面那一个部分为有序的数组,我们每次将无序数组的第一个数插入到后面该有的位置即有序数组中,计算移动距离
复杂度
我们可以用遍历无序数组中每一个数将其放入有序数组中,用树来储存有序的数组让我们可以以logN查找到位置并插入总复杂度O(NlogN)
