题解：P1966 [NOIP2013 提高组] 火柴排队

· · 题解

题目传送门

思路

首先观察要最小化的式子 \sum (a_i-b_i)^2，由于 (a_i-b_i)^2=a_i^2+b_i^2-2a_ib_i，所以有 \sum(a_i-b_i)^2 =\sum(a_i^2+b_i^2-2a_ib_i)=\sum a_i^2+\sum b_i^2-2\sum a_ib_i。

由于 \sum a_i^2 和 \sum b_i^2 无论如何排列火柴都不会改变，所以问题转化为最大化 \sum a_ib_i。可以证明，把两个序列排序后，对每个 k，将第 k 小的 a_k 元素与第 k 小的 b_k 元素配对，这样得到的 \sum a_ib_i 是最大的。

然后考虑如何计算答案，可以发现在第 1 列交换和在第 2 列中交换是等价的，所以只考虑对一列进行交换。

首先排序，然后计算出两个数组 c_i 和 d_i， c_i 表示第 1 列中第 i 个元素在第 1 列中是第 c_i 大的， d_i 表示第 2 列中第 i 个元素在第 2 列中是第 d_i 大的。由此，问题便转化为至少需要交换多少个相邻元素，使得 c_i 序列变成 d_i 序列。

这里由于两个数组都是一个排列，所以可以先做一个映射，然后就用归并排序求逆序对就可以了。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
const int mod=1e8-3;
int a[N],b[N],c[N],d[N],r[N];
long long ans=0;
map<int,int> ai;
map<int,int> bi;
map<int,int> m;
void read(int &x){ 
    int f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f;
}
void msort(int left,int right){//归并排序求逆序对
    if(left==right)return;
    int mid=(left+right)/2;
    msort(left,mid);
    msort(mid+1,right);
    int i=left,j=mid+1,k=left;
    while(i<=mid&&j<=right){
        if(a[i]<=a[j]){
            r[k]=a[i];
            k++;
            i++;
        }else{
            r[k]=a[j];
            k++;
            j++;
            ans=(ans+mid-i+1)%mod;//记得取模
        }
    }
    while(i<=mid){
        r[k]=a[i];
        k++;
        i++;
    }
    while(j<=right){
        r[k]=a[j];
        k++;
        j++;
    }
    for(int i=left;i<=right;i++) a[i]=r[i];
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        read(a[i]);
        c[i]=a[i];//记录c[i]
        ai[a[i]]=i;
    }
    for(int i=1;i<=n;i++){
        read(b[i]);
        d[i]=b[i];//记录d[i]
        bi[b[i]]=i;
    }
    sort(c+1,c+1+n);
    sort(d+1,d+1+n);
    for(int i=1;i<=n;i++){
        b[bi[d[i]]]=i;
        a[ai[c[i]]]=i;
    }
    for(int i=1;i<=n;i++)m[b[i]]=i;//映射
    for(int i=1;i<=n;i++)a[i]=m[a[i]];
    msort(1,n);//求逆序对
    printf("%lld",ans%mod);
    return 0;
}