首页 > 其他 > 详细

NOIP2013火柴排队

时间:2018-07-13 13:11:45      阅读:135      评论:0      收藏:0      [点我收藏+]

题目描述

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

其中 ai 表示第一列火柴中第 i 个火柴的高度,bi 表示第二列火柴中第 i 个火柴的高度。

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

输入输出格式

输入格式:

 

输入文件为 match.in。

共三行,第一行包含一个整数 n,表示每盒中火柴的数目。

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

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

 

输出格式:

 

输出文件为 match.out。

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

 

输入输出样例

输入样例#1:
【输入输出样例 1】
4
2 3 1 4
3 2 1 4
【输入输出样例 2】
4
1 3 4 2
1 7 2 4
输出样例#1:
【输入输出样例 1】
1
【输入输出样例 2】
2

说明

【输入输出样例说明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 ≤火柴高度≤ maxlongint

 

//堆排(求逆序对数)

Merge_Sort函数请见洛谷p1774最接近神的人

 

#include<bits/stdc++.h>
using namespace std;
int i,j,n,Ans;

int c[100010];
int d[100010];

struct node
{
    int num,x;//num是数字,x是它的位置
}a[100010],b[100010];

bool cmp(node a,node b)
{
    return a.num<b.num;
}

void Merge_Sort(int L, int R)
{
    if (L==R) return;
    int Mid=(L+R)/2;
    Merge_Sort(L,Mid);     Merge_Sort(Mid+1,R);
    int P=L; int Q=Mid+1,T=L;
    while (P<=Mid || Q<=R)
    {
      if (Q>R || P<=Mid && d[P]<=d[Q])     
        {c[T++]=d[P]; P++; }
        else
        {c[T++]=d[Q]; Q++; Ans=(Ans+Mid-P+1)%99999997;}
    }
    for (int i=L; i<=R; i++) d[i]=c[i];
}


int main()
{
    freopen("match.in","r",stdin);
    freopen("match.ans","w",stdout);
    cin>>n;
    for (i=1; i<=n; i++)
    {
      cin>>a[i].num;
      a[i].x=i;
    }
    for (i=1; i<=n; i++)
    {
       cin>>b[i].num;
       b[i].x=i;
    }
    sort(a+1,a+n+1,cmp);
    sort(b+1,b+n+1,cmp);
    for (i=1; i<=n; i++) d[a[i].x]=b[i].x;
    Merge_Sort(1,n);
    cout<<Ans%99999997;
    return 0;
}
    
    

NOIP2013火柴排队

原文:https://www.cnblogs.com/SandStorm/p/9304301.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!