P1966 [NOIP 2013 提高组] 火柴排队

根据题意我们可以得到两列火柴的距离公式
$$\sum_{i=1}^{n}(a_i-b_i)^2=\sum_{i=1}^{n}a_i^2+\sum_{i=1}^{n}b_i^2-\sum_{i=1}^{n}a_ib_i$$
我们可以发现无论序列中 $a_i$ $b_i$顺序怎么变化，$\sum_{i=1}^{n}a_i^2+\sum_{i=1}^{n}b_i^2$ 是一定不变 的，而想让他们的距离最小，我们便需要让 $\sum_{i=1}^{n}a_ib_i$最大，这里便需要用到排序不等式

• 排序不等式：正序和>=乱序和>=逆序和

正序代表两个数组要么同时单调递增，要么同时单调递减，逆序则为它们一个同时单调递增，一个同时单调递减

证明：设有两个数组 $A$ $B$,他们的元素分别为 $a_1\ a_2 \ a_3 …a_n$ 和 $b_1\ b_2 \ b_3 …b_n$ ,$a_1\geq a_2\geq a_3…\geq a_n$ $b_1 \geq b_2 \geq b_3…\geq b_n$($a_1\leq a_2\leq a_3…\leq a_n$ $b_1 \leq b_2 \leq b_3…\leq b_n$ )

则有
$$\sum_{i=1}^{i<=n-i+1}(a_i-a_{n-i+1})(b_i-b_{n-i+1})\geq0 \\ \sum_{i=1}^{i<=n-i+1}a_ib_i+a_{n-i+1}b_{n-i+1}-a_ib_{n-i+1}-b_ia_{n-i+1}\geq0 \\ \sum_{i=1}^{n}a_ib_i-\sum_{i=1}^{i<=n }a_ib_{n-i+1}\geq0 \\ \sum_{i=1}^{n}a_ib_i\geq\sum_{i=1}^{i<=n}a_ib_{n-i+1}$$

当且仅当 $a_1=a_2=a_3=…a_n$ 或 $b_1=b_2=b_3=…b_n$ 时等号成立，所以正序和>=逆序和

于是我们就需要两盒火柴按相对大小一一匹配，大对大，小对小

对于样例

4
2 3 1 4
3 2 1 4

毫无疑问，我们要对这两个数组排序，排序后数组为

这时候我们就可以得到两列火柴的最短距离，但题目并没有让我们求这个最短距离，而是让我们求这个交换次数，由于两列火柴的已排列整齐，所以我们就不需要 $v$ 这一行，直接把 $id$ 取出来分析

为了达成我们的目标，我们要做的便是使 $A_{id}$ $B_{id}$ 一一对应即 $A_{id}=B_{id}$ ,这是因为下标编号的变化代表火柴位置的变化,原来两列火柴是编号是一一对应的，而我们排序后使它的值一一对应，改变了编号，所以我们要求改变的次数，即将现在不对应的编号变为原来对应的编号。在此，我们可以用一个新的数组 $C$ 来存储 $A_{id}$ 与 $B_{id}$ 的对应关系，使 $C[A_{id}]=B_{id}$

因为题目中说只有每列火柴中相邻两根火柴的位置都可以交换，所以我们交换火柴的过程相当于一个冒泡排序，冒泡排序每一次交换, 就是交换一个相邻的逆序对，该交换不会影响到其它的逆序对，所以可以计算冒泡排序在排序过程一共进行了多少次交换，由此得出数组的逆序对数，所以我们所要的答案便是最终处理的 $C$ 中逆序对的数量。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,mod=1e8-3;
int n,c[N],ans;
struct node{
    int id,v;
}a[N],b[N];
bool cmp(node x,node y){
    return x.v<y.v;
}
int nsort(int bxh[],int l,int r){//归并排序统计逆序对
    if(l>=r){
        return 0;
    }
    int mid=(l+r)>>1;
    int res=0;
    res=(res+nsort(bxh,l,mid))%mod;
    res=(res+nsort(bxh,mid+1,r))%mod;
    int temp[N];
    int i=l,j=mid+1,k=1;
    while(i<=mid&&j<=r){
        if(bxh[i]<=bxh[j]){
            temp[k++]=bxh[i++];

        }else{
            temp[k++]=bxh[j++];
            res=(res+mid-i+1)%mod;   
        }
    }
    while(i<=mid){
        temp[k++]=bxh[i++];
    }
    while(j<=r){
        temp[k++]=bxh[j++];
    }
    for(int i=l,k=1;i<=r;i++){
        bxh[i]=temp[k++];
    }
    return res;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].v;
        a[i].id=i;
    }
    for(int i=1;i<=n;i++){
        cin>>b[i].v;
        b[i].id=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].id]=a[i].id;//关系映射
    }
    ans=nsort(c,1,n);
    cout<<ans;
    return 0;
}