题目描述

题目的意思：min∑i=1n(ai−bi)2

展开：min{∑（ai^2+bi^2-2aibi）}=min{∑ai^2+∑bi^2-∑2aibi}

仔细观察，可以发现∑ai^2和∑bi^2的值是不会变的，所以只能在∑2aibi上做文章。

为使得和最小，那么∑2aibi要最大，本题的模型就转变为max{∑ai*bi}。(2为常数，可省略)

数学分析暂时告一段落，下面讲一讲我对本题的一句话的特殊看法

c[b[i].loc]=a[i].loc
这句话很重要，但是楼下说的都不太准确。

这并不是映射，其实这里利用了下标的单调升序。

可以发现c数组下标都是1~n，b数组中每个数的顺序也都是1~n的正整数，a数组同样如此。

那么对c数组进行归并排序之后，可以发现c数组中的值就是：c[1]=1,c[2]=2......c[n]=n对吧？

那么也就是说，对c数组进行归并排序就是为了让c[i]=i，也就是说，让b数组中第i小的数和a数组中第i小的数在同一个位置。

证明为什么让b数组中第i小的数和a数组中第i小的数在同一个位置就一定最优?

接着上面的数学证明

a<b c<d

根据以上猜测，则ac+bd一定是最大的。利用反证法。

若ac+bd不是最大的，那么一定有比它更大的，只有ad+bc

ac+bd<ad+bc

ac-ad<bc-bd

a(c-d)<b(c-d)//c-d<0

a>b（？？？）

得出矛盾。所以从最简单的情况推出_b数组中第i小的数和a数组中第i小的数在同一个位置_就是最优的。

样例

输入
4
2 3 1 4
3 2 1 4
输出
1

算法1

(逆序对,归并排序,树状数组) $O(nlogn)$

C++ 代码

#include<bits/stdc++.h>
//#pragma GCC optimize(2)//O2优化
using namespace std;
typedef long long ll;
const int N=100000+10,INF=99999997;
int n,c[N],d[N],ans;
struct asd
{
    int x,y;
}a[N],b[N];
int read()
{
    int res=0,ch=getchar();
    while(!isdigit(ch)&&ch!=EOF)
    {
        ch=getchar();
    }
    while(isdigit(ch))
    {
        res=(res*10)+(ch-'0');
        ch=getchar();
    }
    return res;
}
bool bll(asd l,asd r)
{
    return l.x<r.x;
}
void dsa(int l,int r)
{
    if(l>=r)
    {
        return;
    }
    int m=(l+r)>>1;
    dsa(l,m);
    dsa(m+1,r);
    int i,j,k;
    for(i=l,j=m+1,k=l;i<=m&&j<=r;)
    {
        if(c[i]>c[j])
        {
            ans=(ans+r-j+1)%INF;
            d[k]=c[i];
            i++;
            k++;
        }
        else
        {
            d[k]=c[j];
            k++;
            j++;
        }
    }
    for(;i<=m;i++,k++)
    {
        d[k]=c[i];
    }
    for(;j<=r;j++,k++)
    {
        d[k]=c[j];
    }
    for(i=l;i<=r;i++)
    {
        c[i]=d[i];
    }
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        a[i].x=read();
        a[i].y=i;
    }
    for(int i=1;i<=n;i++)
    {
        b[i].x=read();
        b[i].y=i;
    }
    sort(a+1,a+1+n,bll);
    sort(b+1,b+1+n,bll);
    for(int i=1;i<=n;i++)
    {
        c[b[i].y]=a[i].y;
    }
    dsa(1,n);
    printf("%d\n",ans);
    return 0;
}

只供参考，禁止复制。版权所有，违者必究。