首页 > 其他 > 详细

P1966 NOIP2013T2 火柴排队求逆序对

时间：2019-08-16 23:18:54 阅读：136 评论：0 收藏：0 [点我收藏+]

题意：题目给出两个等长的序列，求交换两个序列的最小次数，使两个序列之间的值满足 sum(ai-bi)^2 最小；

解法：归并排序/树状数组+求逆序对

1.归并排序/树状数组：这两种方式都是可以较快地求出逆序对个数

2.求逆序对：因为只有当两个序列相对的数值都是其本序列中的相同等级的数，才能使等式最小。而移动两个序列的同一个数相当于没有移动，故题目可转化为将一个序列转变成为另一个序列的最小移动次数。此时不难看出 a序列转变为 b序列的最小移动次数就是 a的逆序对个数；

P1966 NOIP2013T2 火柴排队求逆序对

原文：https://www.cnblogs.com/nnezgy/p/11366297.html

踩

(0)

赞

(0)

举报

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)

最新文章

更多>

教程昨日排行

更多>

友情链接

汇智网 PHP教程插件网

关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com

© 2014 bubuko.com 版权所有

打开技术之扣，分享程序人生！