hrbust 1079 I can do it(贪心)

I can do it Time Limit: 1000 MSMemory Limit: 65536 K Total Submit: 254(115 users)Total Accepted: 123(94 users)Rating: Special Judge: No 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 (can't 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. (2 <= 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 3 1 100 2 100 3 1

Sample Output

Case 1: 3

肯定要选择一个大的。。。

所以我们只需要从两边分别选择一个最小的a（b）然后再选择一个位置不相等的最大的b（a）

#include<stdio.h> #include<algorithm> using namespace std; struct data { int num,pos; }a[1000003],b[1000333]; int cmp(data n,data m) { return n.num<m.num; } int main() { int T; scanf("%d",&T); int t=0; while(T--) { int n; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d%d",&a[i].num,&b[i].num); a[i].pos=b[i].pos=i; } sort(a,a+n,cmp); sort(b,b+n,cmp); int res1,res2,res; res1=a[0].num; res1+=(b[n-1].pos==a[0].pos)?b[n-2].num:b[n-1].num; res2=b[0].num; res2+=(a[n-1].pos==b[0].pos)?a[n-2].num:a[n-1].num; res=min(res1,res2); printf("Case %d: %d\n",++t,res); } }