3286 火柴排队

2013年NOIP全国联赛提高组

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 钻石 Diamond

题目描述 Description

涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为：
，其中 ai表示第一列火柴中第 i 个火柴的高度，bi表示第二列火柴中第 i 个火柴的高度。
每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 99,999,997 取模的结果。

输入描述 Input Description

共三行，第一行包含一个整数 n，表示每盒中火柴的数目。
第二行有 n 个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。
第三行有 n 个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。

输出描述 Output Description

输出共一行，包含一个整数，表示最少交换次数对 99,999,997 取模的结果。

样例输入 Sample Input

[Sample 1]
4
2 3 1 4
3 2 1 4
[Sample 2]
4
1 3 4 2
1 7 2 4

样例输出 Sample Output

[Sample 1]
1
[Sample 2]
2

数据范围及提示 Data Size & Hint

【样例1说明】
最小距离是 0，最少需要交换 1 次，比如：交换第 1 列的前 2 根火柴或者交换第 2 列的前 2 根火柴。
【样例2说明】
最小距离是 10，最少需要交换 2 次，比如：交换第 1 列的中间 2 根火柴的位置，再交换第 2 列中后 2 根火柴的位置。
【数据范围】
对于 10%的数据， 1 ≤ n ≤ 10；
对于 30%的数据，1 ≤ n ≤ 100；
对于 60%的数据，1 ≤ n ≤ 1,000；
对于 100%的数据，1 ≤ n ≤ 100,000，0 ≤火柴高度≤ 2^31 - 1。

分类标签 Tags 点此展开

分治贪心逆序对归并排序大陆地区 NOIP全国联赛提高组 2013年

题目大意：给定两个长度为n的序列，序列中相邻的数可以相互交换。求至少交换多少次才能使火柴之间的距离和最小。

思路：可以用排序不等式证明，当每一根火柴与在各自排完序的序列中的序号相同者配对时，才有最小距离和。对于一个序列a，先确定其中元素相对于整个序列的位置，再用编号1、2、3进行定位，再对序列b中元素按已经在a中标好的标号与排名的对应关系对b进行标号，最后就是求逆序对个数了。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 100100
#define mod 99999997
int a[N],b[N],tmpa[N],tmpb[N],ranka[N],rankb[N],has[N];
int id[N],c[N],n;
int ans=0;
void merge_sort(int l,int r){
    if(l==r) return ;
    int mid=(l+r>>1);
    merge_sort(l,mid);merge_sort(mid+1,r);
    int p=l,j=mid+1,q=l;
    while(p<=mid&&j<=r){
        if(id[p]>id[j])
            ans=(ans+(mid-p+1)%mod)%mod,
            c[q++]=id[j++];
        else
            c[q++]=id[p++];
    }
    while(p<=mid) c[q++]=id[p++];
    while(j<=r) c[q++]=id[j++];
    for(int i=l;i<=r;i++) id[i]=c[i];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",a+i);
    for(int i=1;i<=n;i++) scanf("%d",b+i);
    memcpy(tmpa,a,sizeof tmpa);
    memcpy(tmpb,b,sizeof tmpb);
    sort(tmpa+1,tmpa+n+1);
    sort(tmpb+1,tmpb+n+1);
    for(int i=1;i<=n;i++) ranka[i]=lower_bound(tmpa+1,tmpa+n+1,a[i])-(tmpa+1);
    for(int i=1;i<=n;i++) rankb[i]=lower_bound(tmpb+1,tmpb+n+1,b[i])-(tmpb+1);
    for(int i=1;i<=n;i++) has[ranka[i]]=i;
    for(int i=1;i<=n;i++) id[i]=has[rankb[i]];
    merge_sort(1,n);
    printf("%d
",ans);
    return 0;
}