火柴排队（NOIP2913）

传送法阵

（老是放传送门，都用腻了，换一个）

这道题，想通了就不难。

其实主要就是数学分析。

我们来对目标式进行化简：

∑(a-b)²=∑(a²-2ab+b²)

这里用了完全平方公式（应该是这个吧！）

那么我们知道对a/b的平方求和是一个定值。

所以我们要关注的就是∑(-2ab)，我们要求它的最小值，也就是求∑(ab)的最大值（前面有个负号）。

那么什么时候最大呢？

我们都知道排序不等式，也就是说顺序和大于乱序和大于倒序和。

所以最大的情况就是把a中第i大的和b中第i大的搭配到一起。

至此，这道题基本已经做了（liao）。

我们只要弄个数组c保存b中每个数对应的a中的数的编号即可。

然后对c进行归并排序，求他的逆序对的距离和，也就是我们要的结果。

其实代码最长的是归并排序，有点喧宾夺主的感觉。

代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mod=;
struct matches{
    long long l;
    int num;
};
int n; 
int ans=;
int cmp(matches a,matches b){
    return a.l<b.l;
}
matches a[],b[];
int c[],d[];
void comsort(int l,int r){
    if(l>=r){
        return;
    }
    int mid=(l+r)>>;
    comsort(l,mid);
    comsort(mid+,r);
    int forms[mid-l+],backs[r-mid];
    for(int i=;i<mid-l+;i++){
        forms[i]=c[i+l];
    }
    for(int i=;i<r-mid;i++){
        backs[i]=c[i+mid+];
    }
    int curl=,curr=;
    for(int i=l;i<=r;i++){
        if(curl<mid-l+&&curr<r-mid){
            if(forms[curl]>backs[curr]){
                ans=(ans+mid-l-curl+)%mod;
                c[i]=backs[curr++];
            }else{
                c[i]=forms[curl++];
            }
        }else if(curr<r-mid){
            for(;i<=r;i++){
                c[i]=backs[curr++];
            }
            break; 
        }else{
            for(;i<=r;i++){
                c[i]=forms[curl++];
            }
            break;
        }

    }
}
int main(){
    scanf("%d",&n);
    for(int i=;i<n;i++){
        int x;
        scanf("%lld",&x);
        a[i].l=x;
        a[i].num=i;
    }
    for(int i=;i<n;i++){
        int x;
        scanf("%lld",&x);
        b[i].l=x;
        b[i].num=i;
    }
    sort(a,a+n,cmp);
    sort(b,b+n,cmp);
    for(int i=;i<n;i++){
        c[b[i].num]=a[i].num;
    }
    comsort(,n-);
    printf("%d",ans%mod);
    return ;
}