#534. 「多校联考 2022 Round 3」对立

内存限制:256 MiB 时间限制:1000 ms 输入文件:opposite.in 输出文件:opposite.out
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

题目背景

互联网将整个世界连接起来,各个寡头公司却乐此不疲地创造一座又一座信息孤岛,在孤岛与孤岛之间挑拨对立。

某平台 W 上正上演如是一幕。

题目描述

W 平台上有 2n 个浏览者,每个浏览者都有各自的影响力, W 平台将他们两两成对,组成 n 对。然后将每一对分别划分到 A,B 两个阵营。 W 平台预计 A,B 两个阵营的内部极差的乘积为该事件的不确定度。 W 平台当然试图最小化不确定度。

形式化表述:

有 n 对数字,对于每一对数字,将一个加入集合 A ,另一个加入集合 B 。

你的任务是最小化

其中 表示集合 S 的最大/最小值。

输入格式

第 1 行,一个整数 n 。

第 2 ~n+1 行,每行两个整数,代表当前这对人的影响力。

输出格式

一行,表示你的答案。

样例

样例输入 #0

3
1 2
3 4
5 6

样例输出 #0

15

样例 1~4

见附加文件。

样例解释

集合 A 为 {1,3,6} 或{1,4,6} 。

集合 B 为 {2,4,5} 或{2,3,5} 。

数据范围与提示

对于所有的数据:

测试点 数据范围 特殊性质
1,2 n=20
3 n=100
4 n=1000
5 n= 19998 A
6,7 n=19999 B
8,9,10 n=20000

特殊性质 A :保证存在一种排列方式,使得排在后面的人影响力大于排在前面的人。

特殊性质 B :保证每个人影响力互不相同。