p1966专题

P1966 [NOIP2013 提高组] 火柴排队

洛谷的一道原题,方法有很多,树状数组以及排序,对刚学树状数组的人来说用排序会比较好理解。 本题最重要的结论就是,要保证两个数组中相同位置的差最小,但是不一定两个数组中数值相同,所以只需要保证相同位置放的数都是当前数组中第i小的,也就是第一个数组里面第i小数和第二个数组中第i的数放的位置要相同,这个地方搞明白之后,只需要找到最小移动次数,这个时候就简单了用归并排序+逆序对即可。 #inclu