首页 > ACM题库 > HDU-杭电 > HDU 3552-I can do it![解题报告]HOJ
2014
11-05

HDU 3552-I can do it![解题报告]HOJ

I can do it!

问题描述 :

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 , 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)

输出:

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)

样例输入:

1
3
1 100
2 100
3 1

样例输出:

Case 1: 3

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 111111;
struct node {
	int a,b;
	void input(void) { scanf("%d%d",&a,&b); }
	bool operator<(const node &r)const { return a>r.a; }
}p[N];
int main(void) {
	int n,t;
	scanf("%d",&t);
	for(int cas=1;cas<=t;cas++) {
		scanf("%d",&n);
		for(int i=1;i<=n;i++) p[i].input();
		sort(p+1,p+n+1);
		int res=0x7fffffff;
		int b=0;
		p[n+1].a=0;
		for(int i=1;i<=n+1;i++) {
			b=max(b,p[i-1].b);
			res=min(res,p[i].a+b);
		}
		printf("Case %d: %d\n",cas,res);
	}
	return 0;
}