「题解」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]$,求其逆序对即可。

代码

#include<cstdio>
#include<algorithm>
const int MAXN = 100000 + 6,MOD = 99999997;
int A[MAXN],B[MAXN],AA[MAXN],BB[MAXN],Q[MAXN],delta[MAXN],ans;
inline bool cmp1(int i,int j){return A[i] < A[j];}
inline bool cmp2(int i,int j){return B[i] < B[j];}
void mergeSort(int l,int r){
    if(l == r) return;
    int mid = (l + r) / 2;
    mergeSort(l,mid);mergeSort(mid + 1,r);
    int i = l,j = mid + 1,k = l;
    while(i <= mid && j <= r){
        if(Q[i] <= Q[j]) delta[k] = Q[i],k++,i++;
        else delta[k] = Q[j],k++,j++,ans += mid - i + 1,ans %= MOD;
    }
    while(i <= mid) delta[k] = Q[i],k++,i++;
    while(j <= r) delta[k] = Q[j],k++,j++;
    for(int i = l;i <= r;i++) Q[i] = delta[i];
}

int main(){
    int n;scanf("%d",&n);
    for(int i = 1;i <= n;i++) scanf("%d",&A[i]),AA[i] = i;
    for(int i = 1;i <= n;i++) scanf("%d",&B[i]),BB[i] = i;
    std::sort(AA + 1,AA + 1 + n,cmp1);
    std::sort(BB + 1,BB + 1 + n,cmp2);
    for(int i = 1;i <= n;i++) Q[AA[i]] = BB[i];
    mergeSort(1,n);
    printf("%d",ans % MOD);

    return 0;
}