首页 > 代码库 > 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(贪心)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。