UC知道NOIP2008配对
来源：百度知道 编辑：UC知道 时间：2024/06/03 19:55:26
NOIP2008四川 配对:
******************用PASCAL写************************
描述 Description
你有n个整数Ai和n个整数Bi。你需要把它们配对，即每个Ai恰好对应一个Bp[i]。要求所有配对的整数差的绝对值之和尽量小，但不允许两个相同的数配对。例如A={5,6,8}，B={5,7,8}，则最优配对方案是5←→8, 6←→5, 8←→7，配对整数的差的绝对值分别为3, 1, 1，和为5。注意，5←→5，6←→7，8←→8是不允许的，因为相同的数不许配对。
输入格式 Input Format
第一行为一个正整数n，接下来是n行，每行两个整数Ai和Bi，保证没有任何两行完全相同，即对于不同的i和j，不可能有Ai=Aj或Bi=Bj。
输出格式 Output Format
输出一个整数，即配对整数的差的绝对值之和的最小值。如果无法配对，输出-1。
样例输入 Sample Input
3
5 5
6 7
8 8
样例输出 Sample Output
5
时间限制 Time Limitation
每个点时限1S。
注释 Hint
【数据规模】
30%的数据满足：n <= 10000
100%的数据满足：1 <= n <= 100000，Ai和Bi均为1到1000000000之间的整数。
来源 Source
四川08省选
******************用PASCAL写************************
描述 Description
你有n个整数Ai和n个整数Bi。你需要把它们配对，即每个Ai恰好对应一个Bp[i]。要求所有配对的整数差的绝对值之和尽量小，但不允许两个相同的数配对。例如A={5,6,8}，B={5,7,8}，则最优配对方案是5←→8, 6←→5, 8←→7，配对整数的差的绝对值分别为3, 1, 1，和为5。注意，5←→5，6←→7，8←→8是不允许的，因为相同的数不许配对。
输入格式 Input Format
第一行为一个正整数n，接下来是n行，每行两个整数Ai和Bi，保证没有任何两行完全相同，即对于不同的i和j，不可能有Ai=Aj或Bi=Bj。
输出格式 Output Format
输出一个整数，即配对整数的差的绝对值之和的最小值。如果无法配对，输出-1。
样例输入 Sample Input
3
5 5
6 7
8 8
样例输出 Sample Output
5
时间限制 Time Limitation
每个点时限1S。
注释 Hint
【数据规模】
30%的数据满足：n <= 10000
100%的数据满足：1 <= n <= 100000，Ai和Bi均为1到1000000000之间的整数。
来源 Source
四川08省选
DP...你这照搬vj1530...
其实我本来也不会做,可是有大牛告诉我了..
F[i]表示前i个匹配好的最小差值,然后转移枚举最后三个的全排列..
我也不知道为什么是对的..
我是这样想的:如果没有'不能等于'的限制，那就是贪心，大的配大的，小的配小的。有了限制之后，有时就不得不有交叉配对，这些都特殊处理一下就可以了。不知道想法对不对，看一下把~