/ Vijos / 题库 /

配对

配对

描述

你有n个整数Ai和n个整数Bi。你需要把它们配对,即每个Ai恰好对应一个Bi。要求所有配对的整数差的绝对值之和尽量小,但不允许两个相同的数配对。例如A={5,6,8},B={5,7,8},则最优配对方案是5←→8, 6←→5, 8←→7,配对整数的差的绝对值分别为3, 1, 1,和为5。注意,5←→5,6←→7,8←→8是不允许的,因为相同的数不许配对。

格式

输入格式

第一行为一个正整数n,接下来是n行,每行两个整数Ai和Bi,保证没有任何两行完全相同,即对于不同的i和j,不可能有Ai=Aj或Bi=Bj。

输出格式

输出一个整数,即配对整数的差的绝对值之和的最小值。如果无法配对,输出-1。

样例1

样例输入1

3
5 5
6 7
8 8

样例输出1

5

限制

每个点时限1S。

提示

【数据规模】
30%的数据满足:n <= 10000
100%的数据满足:1 <= n <= 100000,Ai和Bi均为1到1000000000之间的整数。

来源

四川08省选

信息

ID
1530
难度
7
分类
动态规划 点击显示
标签
递交数
356
已通过
65
通过率
18%
被复制
1
上传者

相关

在下列训练计划中:

RP++分类题库