b345: NOIP2013 Day1.2.火柴排队
Tags :
Accepted rate : 22人/26人 ( 85% ) [非即時]
評分方式:
Tolerant

最近更新 : 2015-08-05 16:34

Content

涵涵有两盒火柴,每盒装有 n 根火柴,每根火柴都有一个高度。现在将每盒中的火柴各自排成一列,同一列火柴的高度互不相同,两列火柴之间的距离定义为:$\sum_{i=1}^n(a_i-b_i)^2$,其中 ai 表示第一列火柴中第 i 个火柴的高度,bi 表示第二列火柴中第 i 个火柴的高度。

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

 

Input

输入文件为 match.in

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

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

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

Output

输出文件为 match.out

输出共一行,包含一个整数,表示最少交换次数对 99,999,997 取模的结果
Sample Input
例 1:
4               1
2 3 1 4
3 2 1 4	1

例 2:
4
1 3 4 2
1 7 2 4
Sample Output
例 1:
1

例 2:
2
測資資訊:
記憶體限制: 128 MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1K
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <1M
公開 測資點#5 (10%): 1.0s , <1M
公開 測資點#6 (10%): 1.0s , <1M
公開 測資點#7 (10%): 1.0s , <1M
公開 測資點#8 (10%): 1.0s , <1M
公開 測資點#9 (10%): 1.0s , <10M
Hint :
Tags:
出處:
NOIP2013提高组Day1第二题 [管理者:
htbb (海豚爸爸)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」