本文共 2851 字，大约阅读时间需要 9 分钟。

题目描述

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

其中 $a_i$ 表示第一列火柴中第 $i$ 个火柴的高度，$b_i$ 表示第二列火柴中第 $i$ 个火柴的高度。

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

输入格式

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

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

输出格式

一个整数，表示最少交换次数对 $10^8-3$ 取模的结果。

输入输出样例

输入

41 3 4 21 7 2 4

输出

2

数据范围

$1\le n\le 10^5$，$0\le$ 火柴高度 $\le 2^{31}。$

分析

好，一开始我们数学推一波。

欲求 $min(\sum (a_i-b_i{)}^2)(1\le i\le n)$。 即求 $min(\sum a_i^2+\sum b_i^2-\sum 2a_i{b}_i)$。 因为 $\sum a_i^2$ 和 $\sum b_i^2$为定值。 即求$max(\sum 2a_i{b}_i)$。 即求$max(\sum a_i{b}_i)$。 令$A_1>A_2$， $B_1>B_2$。 _{按照生活常识}易知 $A_1{B}_2+A_2{B}_1\le A_1{B}_1+A_2{B}_2$ 好吧如果你问为什么， 我也不知道 把$A_2{B}_1$移到不等式右边，$A_1{B}_1$移到不等式左边，提个$A_1$，$A_2$出来你总知道了吧。 说得通俗一点，就是要让最大乘最大，最小乘最小，才能得到整体最大。 做法就很明显了，将两数组排序，让相同下标的两数一一对应。输入时令$a[i].num=i$，$b[i].num=i$。（离散化）我们需要在两数组从小到大排序后仍使$a[i].num==b[i].num$。定义$mp$数组$mp[a[i].num]=b[i].num$。则需使$mp[i]=i$。即求从小到大排序$mp$数组的最小步数。即求此数组中逆序对的个数。（板子） 好的，分析完毕。

代码

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
       
      
     
    
   

谢谢观看，欢迎指出错误&问问题。