首页 > 代码库 > NBUT 2014 F Team of Slime
NBUT 2014 F Team of Slime
题目链接:http://acm.nbut.edu.cn/Problem/view.xhtml?id=1557
题意:给出n个不相同且分布在1-n之间的正整数组成的队列,每次可以将任一个数放到队首,问最少需要多少次可以将队列变为升序?
分析:
(1)一种方法是对于每个有较大数在前面的数放到队首,然后将后面比它小的数再按照从大到小的顺序放到队首,这样就能将队列变为升序,实现可以用线段树维护每个数的逆序数,可惜这样做不是最优的结果;
(2)考虑下界:考虑不需要移动的数,最大数n无论如何是不需要移的,n-1如果出现在n前面也是无论如何不需要移的,而如果出现在n后面则无论如何是必须要移的,类推下去,会发现找一个n结束的按出现位置递增的序列,这个序列的数都是不需要移的,除此之外的数都是必须要移的,所以最小的移动次数是n减这个序列的长度。
可以通过倒着遍历一遍,找出这样的序列,复杂度O(n)。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。