vijos1842(火柴排队)

描述

涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为：∑i=1n(ai−bi)2∑i=1n(ai−bi)2，其中 aiai 表示第一列火柴中第 i 个火柴的高度，bibi 表示第二列火柴中第 i 个火柴的高度。

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

格式

输入格式

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

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

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

输出格式

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

样例输入：

注意：同一列火柴高度互不相同。

定理：冒泡排序的的交换次数为数列的逆序数。

#include <cstdio>

#include <algorithm>

using namespace std;

const int MAXN=;

const int MOD=;

struct Node{

    int h,pos;

}a[MAXN],b[MAXN];

int n;

int bit[MAXN];

int c[MAXN];

bool comp(Node no1,Node no2)

{

    return no1.h < no2.h;

}

void add(int i,int x)

{

    while(i<MAXN)

    {

        bit[i]=(bit[i]+x)%MOD;

        i+=(i&-i);

    }

}

int sum(int i)

{

    int s=;

    while(i>)

    {

        s=(s+bit[i])%MOD;

        i-=(i&-i);

    }

    return s;

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<n;i++)

    {

        scanf("%d",&a[i].h);

        a[i].pos=i+;

    }

    for(int i=;i<n;i++)

    {

        scanf("%d",&b[i].h);

        b[i].pos=i+;

    }

    sort(a,a+n,comp);

    sort(b,b+n,comp);

    for(int i=;i<n;i++)

    {

        c[a[i].pos-]=b[i].pos;

    }

    int res=;

    for(int i=;i<n;i++)

    {

        res=(res+i-sum(c[i]))%MOD;

        add(c[i],);

    }

    printf("%d\n",res);

    return ;

}

巴特西

vijos1842(火柴排队)

描述

格式

输入格式

输出格式

最新文章

热门文章