火柴排隊（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 ;
}