题目链接：https://ac.nowcoder.com/acm/problem/16526

分析：对于两个序列a,b，我们要求火柴之间定义的距离最小${\sum }_1^n(ai-bi{)}^2\backslash sum\_\{1\}^\{n\}(ai-bi)^2$，${\sum }_1^n(ai-bi{)}^2\backslash sum\_\{1\}^\{n\}(ai-bi)^2$=${\sum }_1^{n}a{i}^2\backslash sum\_\{1\}^\{n\}ai^2$+${\sum }_1^{n}b{i}^2\backslash sum\_\{1\}^\{n\}bi^2$-2*${\sum }_1^{n}ai\ast bi\backslash sum\_\{1\}^\{n\}ai*bi$,我们要求距离最小，因为前两项都是固定的，所以总体最小的时候要求最后一项最大即可。要两个序列每一项相乘总体和最大，即是这两个序列有序的时候即可,因此最小交换次数即是二者相对位置的逆序对数，由于火柴高度不一，但是又比较大，所以需要离散化一下数据
   关于求逆序对数，树状数组和归并排序都可以，最后注意取模
离散化

for(int i=1;i<=n;i++) scanf("%lld",&a[i].data),a[i].idx=i;
for(int i=1;i<=n;i++) scanf("%lld",&b[i].data),b[i].idx=i;
//后面记得排个序

对c[b[i].idx]=a[i].idx的理解
   可以发现c数组下标都是1~n，a和b数组同样如此。那么对c数组进行处理之后，可以发现c数组中的值就是：c[1]=1,c[2]=2......c[n]=n，那么也就是说，对c数组进行处理就是为了让c[i]=i，也就是说，让b数组中第i小的数和a数组中第i小的数在同一个位置。

算法一 （归并排序）

Code:

#include<cstdio>
#include<algorithm>
#include<cstring>

#define int long long 
using namespace std;
const int N=1e6+5,mod=1e8-3;

int n;
int c[N],tmp[N];

struct Node{
    int data;
    int idx;
}a[N],b[N];
bool cmp(Node x,Node y){
    return x.data<y.data;
}
int merge_sort(int l,int r){
    if(l>=r) return 0;
    int mid=l+r>>1;
    int res=(merge_sort(l,mid)+merge_sort(mid+1,r))%mod;
    int i=l,j=mid+1,k=1;
    while(i<=mid&&j<=r){
        if(c[i]<=c[j]) tmp[k++]=c[i++];
        else{
            res+=mid-i+1;
            tmp[k++]=c[j++];
        }
    }
    while(i<=mid) tmp[k++]=c[i++];
    while(j<=r) tmp[k++]=c[j++];
    for(int i=l,j=1;i<=r;i++,j++) c[i]=tmp[j];
    return res%mod;
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i].data),a[i].idx=i;
    for(int i=1;i<=n;i++) scanf("%lld",&b[i].data),b[i].idx=i;
    
    sort(a+1,a+1+n,cmp);
    sort(b+1,b+1+n,cmp);
    for(int i=1;i<=n;i++)
        c[b[i].idx]=a[i].idx;
    int ans=merge_sort(1,n);
    printf("%lld\n",ans%mod);
    return 0;
}

算法二 (树状数组)

   当大的数出现在小的数前面时就会产生逆序对。首先将所有位置都初始化为0，我们枚举每一个i的时候将c[i]的位置加1，表示已经存在一个数，前i-1个数肯定已经放进去了，因为大的数总是先出现，所以每次查询sum(c[i])即可，i-sum(c[i])就是答案，然后加起来即可
Code:

#include<cstdio>
#include<algorithm>
#include<cstring>

#define int long long 
using namespace std;
const int N=1e6+5,mod=1e8-3;

int n;
int c[N],tmp[N];
int tr[N];
struct Node{
    int data;
    int idx;
}a[N],b[N];
bool cmp(Node x,Node y){
    return x.data<y.data;
}
int lowbit(int x){
    return x&-x;
}

void add(int x,int c){
    for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c;
}

int sum(int x){
    int res=0;
    for(int i=x;i;i-=lowbit(i)) res+=tr[i];
    return res;
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i].data),a[i].idx=i;
    for(int i=1;i<=n;i++) scanf("%lld",&b[i].data),b[i].idx=i;
    
    sort(a+1,a+1+n,cmp);
    sort(b+1,b+1+n,cmp);
    for(int i=1;i<=n;i++)
        c[b[i].idx]=a[i].idx;
    int res=0;
    for(int i=1;i<=n;i++){
        add(c[i],1);
        res+=i-sum(c[i]);
    }
    printf("%lld\n",res%mod);
    return 0;
}