首页 > 代码库 > HDU3552(贪心)

HDU3552(贪心)

题目是将一系列点对(a,b)分成两个集合,使得A集合的最大a+B集合的最大数b得和最小。

思路:http://blog.csdn.net/dgq8211/article/details/7748078

我真是太差了,担心担心担心...醒来继续努力。

/***********************************************************
	> OS     : Linux 3.13.0-24-generic (Mint-17)
	> Author : yaolong
	> Mail   : dengyaolong@yeah.net
	> Time   : 2014年10月15日 星期三 11时10分06秒
 **********************************************************/
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
pair<int, int> a[100001];
int main()
{
    int cas, n;
    scanf ( "%d", &cas );
    int ind = 0;
    while ( cas-- )
    {
        scanf ( "%d", &n );
        for ( int i = 1; i <= n; i++ )
        {
            scanf ( "%d%d", &a[i].first, &a[i].second );
        }
        sort ( a + 1, a + n + 1 );
        a[0].first = 0;
        a[n + 1].second = 0;
        int ans = 1 << 30, B = 0;
        for ( int i = n; i >= 0; i-- )
        {
            B = max ( B, a[i + 1].second );
            ans = min ( ans, a[i].first + B );
        }
        printf ( "Case %d: %d\n", ++ind, ans );
    }
    return 0;
}


HDU3552(贪心)