hdoj 3552——思考問題

I can do it!
Time Limit: 2000/2000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 749    Accepted Submission(s): 345
Problem Description
Given n elements, which have two properties, say Property A and Property B. For convenience, we use two integers A
i and B
i 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) {A
x}+max
(y∈Set B) {B
y}.
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 A
i and B
i indicate the Property A and Property B of the ith element. (0 <= A
i, B
i <= 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
   
   
   
   

 
Author
HyperHexagon
 
Source
HyperHexagon's Summer Gift (Original tasks)
 
Recommend
zhengfeng
 
各要素にはA、Bの2つの属性があり、X、Yの2つの集合に分けて、X集合の属性Aの最大値と集合Yの属性Bの最大値の和が最小になるように、最小値を出力します.
A値が決定されているため、属性Aの値がAより大きい要素は必ずY集合にあり、bmaxを決定し、ans解を列挙すると考えられる.

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <map>
#include <string>
#include <stack>
#include <cctype>
#include <vector>
#include <queue>
#include <set>
#include <utility>

using namespace std;
//#define Online_Judge
#define outstars cout << "***********************" << endl;
#define clr(a,b) memset(a,b,sizeof(a))
#define lson l , mid  , rt << 1
#define rson mid + 1 , r , rt << 1 | 1
//#define mid ((l + r) >> 1)
#define mk make_pair
#define FOR(i , x , n) for(int i = (x) ; i < (n) ; i++)
#define FORR(i , x , n) for(int i = (x) ; i <= (n) ; i++)
#define REP(i , x , n) for(int i = (x) ; i > (n) ; i--)
#define REPP(i ,x , n) for(int i = (x) ; i >= (n) ; i--)
const int MAXN = 100000 + 500;
const long long LLMAX = 0x7fffffffffffffffLL;
const long long LLMIN = 0x8000000000000000LL;
const int INF = 1 << 29;
const int IMIN = 0x80000000;
const double e = 2.718281828;
#define eps 1e-8
#define DEBUG 1
#define mod 1000000007
typedef long long LL;
const double PI = acos(-1.0);
typedef double D;
typedef pair<int , int> pi;
///#pragma comment(linker, "/STACK:102400000,102400000")__int64 a[10050];
struct Node
{
    int a , b;
}node[MAXN];
bool cmp(const Node & a , const Node & b)
{
    if(a.a != b.a)return a.a < b.a;
    return a.b < b.b;
}
int main()
{
    int n ;
    int t;
    scanf("%d" , &t);
    FORR(kase , 1 , t)
    {
        scanf("%d" , &n);
        FORR(i , 1 , n)
        {
            scanf("%d%d" , &node[i].a , &node[i].b);
        }
        sort(node + 1 , node + n + 1 , cmp);
        int bmax = 0;
//        REPP(i , n - 1, 1)node[i].b = max(node[i].b , node[i + 1].b);
        int ans = node[n].a;
        REPP(i , n , 1)
        {
            bmax = max(bmax , node[i].b);
            ans = min(ans , node[i - 1].a + bmax);
        }
        ans = min(ans , max(node[1].b , bmax));
        printf("Case %d: %d
" , kase , ans);
    }
    return 0;
}