P1966 火柴排队
littlechai
2018-06-02 07:50:38
题目描述
涵涵有两盒火柴，每盒装有 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 - ∑2*ai*bi
所以要使sum最小，即使ai*bi最大，所以要将最大的和最大的放在一起将两列火柴排序后，即可确定第一列火柴对应的第二列火柴，如果我们第一列
火柴不动，只移动第二列火柴，那么就变成了求逆序对的问题。
```cpp
#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;
}
```