「题解」Luogu 1966「火柴排队」

分析

这题可以这样想:

最优解是要求$\sum(A_i-B_i)^2$最小,显然就是要$A_i-B_i$最小,那么利用清晰的脑回路可以得到一个思路:

显然两个数组的第$k$大的位置要相同

然后我们记录$AA[i]=i,BB[i]=i$,然后以$A[i]<A[j]$和$B[i]<B[j]$关键字分别排序$AA[],BB[]$,再令$Q[AA[i]]=BB[i]$,求其逆序对即可。
继续阅读“「题解」Luogu 1966「火柴排队」”