NOIP2013 火柴排队 [洛谷P1966]

题目描述

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

其中 \(a_i\)​ 表示第一列火柴中第 \(i\) 个火柴的高度，\(b_i\) ​表示第二列火柴中第 \(i\) 个火柴的高度。

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

输入输出格式

输入格式：

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

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

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

输出格式：

一个整数，表示最少交换次数对 99,999,997 取模的结果。

思路

求逆序对个数

有一个贪心策略是将 \(a\) 和 \(b\) 排序后形成的 \(a_i\) 与 \(b_i\) 的组合的 $ \sum (a_i-b_i)^2 $ 最小，这里不给出证明 其实我根本不会证明

因为在两个序列中进行交换是等价的，因此我们可以只对 \(b\) 序列进行交换

所以问题就转化为了求将 \(b\) 序列中每一个数移动到和 \(a\) 序列排序后和他对应的数的位置的最少次数

而求这个最少次数的方法是这样的

生成一个 \(ord[]\) 数组，这个数组的第 \(i\) 位代表的含义是：\(b\) 数组中第 \(i\) 个数在排序后对应在 \(a\) 数组中的那个数未排序时在 \(a\) 中原来的的位置

然后求 \(ord\) 数组的逆序对的个数

求逆序对数的方法有很多，可以用归并排序，线段树，如果你高兴的话平衡树也可以

我这里用了归并排序

CODE

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;#define MOD 99999997#define MAXN 100010struct Node{    int val,id;    Node(){}    Node(int val,int id):val(val),id(id){}    bool operator < (const Node &a) const{        return val
        
         57);    n=readc-48;    while((readc=getchar())>=48&&readc<=57) n=n*10+readc-48;}void mergesort(int l,int r){    if(l==r) return;    int mid=(l+r)>>1;    mergesort(l,mid); mergesort(mid+1,r);    int p1=l,p2=mid+1,cnt=l-1;    while(p1<=mid&&p2<=r){        if(ord[p2]