题目描述

涵涵有两盒火柴,每盒装有 nn 根火柴,每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列, 同一列火柴的高度互不相同, 两列火柴之间的距离定义为: ∑(a_i-b_i)^2

其中 a_ia i ​ 表示第一列火柴中第 i i 个火柴的高度, b_ib i ​ 表示第二列火柴中第 ii 个火柴的高度。

每列火柴中相邻两根火柴的位置都可以交换,请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离,最少需要交换多少次?如果这个数字太大,请输出这个最小交换次数对 99,999,997 99,999,997 取模的结果。

输入输出格式

输入格式: 共三行,第一行包含一个整数 nn ,表示每盒中火柴的数目。

第二行有 n n 个整数,每两个整数之间用一个空格隔开,表示第一列火柴的高度。

第三行有 nn 个整数,每两个整数之间用一个空格隔开,表示第二列火柴的高度。

输出格式: 一个整数,表示最少交换次数对 99,999,99799,999,997 取模的结果。

输入输出样例

输入样例#1:

4

2 3 1 4

3 2 1 4

输出样例#1:

1

输入样例#2

4

1 3 4 2

1 7 2 4

输出样例#2

2

说明

【输入输出样例说明1】

最小距离是 00 ,最少需要交换 11 次,比如:交换第 1 1 列的前 22 根火柴或者交换第 22 列的前 2 2 根火柴。

【输入输出样例说明2】

最小距离是 1010 ,最少需要交换 2 2 次,比如:交换第 11 列的中间 2 2 根火柴的位置,再交换第 22 列中后 22 根火柴的位置。

【数据范围】

对于 10\%10% 的数据, 1 ≤ n ≤ 101≤n≤10 ;

对于 30\%30% 的数据, 1 ≤ n ≤ 1001≤n≤100 ;

对于 60\%60% 的数据, 1 ≤ n ≤ 1,0001≤n≤1,000 ;

对于 100\%100% 的数据, 1 ≤ n ≤ 100,000,0 ≤1≤n≤100,000,0≤ 火柴高度 ≤ maxlongint≤maxlongint


∑(a_i-b_i)^2 = ∑ai^2 + ∑bi^2 - ∑2aibi 所以要使sum最小,即使ai*bi最大,所以要将最大的和最大的放在一起将两列火柴排序后,即可确定第一列火柴对应的第二列火柴,如果我们第一列 火柴不动,只移动第二列火柴,那么就变成了求逆序对的问题。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#define MAXN 1000000 + 50
#define ll long long
#define ri register int
#define mod 99999997
using namespace std;
int c[MAXN],t[MAXN];
ll n;
ll ans;
struct edge
{
    int pos;
    ll h;
}a[MAXN],b[MAXN];
bool cmp(edge x,edge y)
{
    return x.h < y.h;
}
inline void re(ll &x)
{
    x = 0;
    int b = 0;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-' ) b = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x << 1) + (x << 3) + ch - '0';
        ch = getchar();
    }
    if(b == -1)
        x *= -1;
}
void merge(int l,int r)
{
    if(l == r) return ;
    int mid = (l + r) >> 1;
    merge(l,mid);
    merge(mid + 1,r);
    int i = l,j = mid + 1,k = l;
    while(i <= mid && j <= r){
        if(c[i] > c[j]){
            t[k ++] = c[j ++];
            ans = (ans + mid - i + 1) % mod;//求逆序对
        }
        else{
            t[k ++] = c[i ++];
        }
    }
    while(i <= mid) t[k ++] = c[i ++];
    while(j <= r) t[k ++] = c[j ++];
    for(ri i = l;i <= r;i ++){
        c[i] = t[i];
    }
}
int main()
{
    re(n);
    for(ri i = 1;i <= n;i ++)
        re(a[i].h),a[i].pos = i;
    for(ri i = 1;i <= n;i ++)
        re(b[i].h),b[i].pos = i;
    sort(a + 1,a + 1 + n,cmp);
    sort(b + 1,b + 1 + n,cmp);
    for(ri i = 1;i <= n;i ++){
        c[a[i].pos] = b[i].pos;
    }
    merge(1,n);
    printf("%lld",ans);
    return 0;
}