【Luogu P1966】火柴排队

按相对大小配对,即a中第一小的配b中第一小的,a中第二小的配b中第二小的,……,以此类推。

样例2模拟:

a 1 3 4 2
b 1 7 2 4

如果按照相同的对相同的配对:

a 1 3 4 2

b 1 7 4 2

距离$=(3-7)^2=16$;

如果按照相对大小配对:

a 1 3 4 2

b 1 4 7 2

距离$=(3-4)^2+(4-7)^2=9$,最小。

将a,b离散化,求出相对大小。

样例1:

a 2 3 1 4

b 3 2 1 4

我们不动b,只移动a里面的火柴棒,这和其它移动方式等价。

因为b是“正确的”,所以我用一个p数组表示相应数字应放在第几个位置:

b 3 2 1 4

p[3]=1,p[2]=2,p[1]=3,p[4]=4

(b被当作1 2 3 4,是“升序”的)

接着,用q数组代替a,对于每个a[i],令q[i]=p[a[i]]。

然后用树状数组/归并排序求逆序对即可。

原文地址:https://www.cnblogs.com/xzs123456/p/10425754.html