Pro.ID21719 TitleI can do it! Title链接http://10.20.2.8/oj/exercise/problem?problem_id=21719 AC5 Submit7 Ratio71.43% 时间&空间限制描述Given n elements, which have two properties, say Property A and Property B. For convenience, we use two integers Ai and Bi to measure the two properties. Your task is, to partition the element into two sets, say Set A and Set B (cannot be empty!), which minimizes the value of max(x∈Set A) {Ax} + max(y∈Set B) {By}. See sample test cases for further details. 输入There are multiple test cases, the first line of input contains an integer denoting the number of test cases. For each test case, the first line contains an integer N, indicates the number of elements. (1 ≤ N ≤ 100000) For the next N lines, every line contains two integers Ai and Bi indicate the Property A and Property B of the ith element. (0 ≤ Ai, Bi ≤ 1000000000) 输出Description Given n elements, which have two properties, say Property A and Property B. For convenience, we use two integers Ai and Bi to measure the two properties. Your task is, to partition the element into two sets, say Set A and Set B (cannot be empty!), which minimizes the value of max(x∈Set A) {Ax} + max(y∈Set B) {By}. See sample test cases for further details. Input There are multiple test cases, the first line of input contains an integer denoting the number of test cases. For each test case, the first line contains an integer N, indicates the number of elements. (1 ≤ N ≤ 100000) For the next N lines, every line contains two integers Ai and Bi indicate the Property A and Property B of the ith element. (0 ≤ Ai, Bi ≤ 1000000000) Output For each test cases, output the minimum value. Sample Input 1 Sample Output Case 1: 3 Source 样例输入1 样例输出Case 1: 3 作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2025-2-3 18:11 , Processed in 0.038369 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
