web analytics

NOIP2013 Day1 火柴排序

题目链接: 随便找一个OJ应该都有吧.QAQ嘤嘤嘤.

分析:

考试拿到数学公式都应该去拆分一下QwQ. 这样可能对解题有帮助>_<

所以我们分析一下这个价值的计算式

 \sum_{i=1}^{n} (a_i - b_i)^2 = \sum_{i=1}^{n} (a_i^2+b_i^2 - 2 \cdot a_i \cdot b_i)

因为 a_i  b_i 都是定值所以我们的值就取决于\sum_{i=1}^{n}( a_i \cdot b_i)

证明:

若存在a>b,c>d,且ac+bd<ad+bc,则a(cd)<b(cd),a<b,与a>b矛盾,所以若a>b,c>d,则ac+bd>ad+bc

 

所以我们只有正序才能保证最优解.

 

所以我们移动只需要固定一个序列.然后用另一个序列的位置.去匹配就好.

交换的次数就是逆序对的数量.

 

 

 

Post a Comment

You must be logged in to post a comment.