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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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;
}
分享到