对于一个闭区间集合{A1,A2……AK}(K>1,Ai≠Aj{i≠j}),我们定义其权值
其中|X|表示X区间的长度;如果X为空集|X|=0。
当然,如果这些闭区间没有交集则权值为0。
给定N个各不相同的闭区间,请你从中找出若干个(至少2个)区间使其权值最大。
输入
第一行一个整数N (2 <= N <= 105)
接下来N行每行两个整数 l r(1<=l<=r<=106),表示闭区间的两个端点。
输出
最大权值
样例输入
4
1 6
4 8
2 7
3 5
样例输出
24
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct Node
{
int l , r;
}node[100005];
int cmp(const Node &a , const Node &b)
{
if(a.l != b.l)
return a.l < b.l;
else if( a.r != b.r)
return a.r < b.r;
}
long long maxx(long long a , long long b)
{
if(a > b)
return a;
else
return b;
}
int main(void)
{
int i , j , n;
cin >> n;
for(i = 0 ; i < n ; ++i)
{
cin >> node[i].l >> node[i].r;
}
sort(node , node+n , cmp);
long long ans = 0;
for(i = 0 ; i < n - 1 ; ++i)
{
for(j = i + 1 ; j < n ; ++j)
{
if(node[j].l >= node[i].r)
break;
ans = maxx(ans,(long long )(node[j].r-node[i].l)*(node[i].r-node[j].l));
}
}
cout << ans << endl;
return 0;
}
分享到:
相关推荐
2012年百度之星初赛题目,仅供参考。有兴趣可以看看
百度之星 2011 初赛 算法设计题 百度之星
原理很简单:取max1,max2 然后分别存到2个不同的数组,之后对这2个数组进行排序后比大小就可以了;
Astar2007百度之星程序设计大赛网络资格赛(初赛) 题。 Astar2007百度之星程序设计大赛网络资格赛(初赛) 题 。
百度之星-编程大赛初赛练习题 题目描述: 一个正整数有可能可以被表示为n(n>=2)个连续正整数之和,如:
百度之星程序设计大赛从2005到2010的初赛、复赛、决赛题目。
2011百度之星试题合集,包括初赛A、B,复赛以及决赛,不含答案。
Astar2006百度之星程序设计大赛题目参考源程序
NOIP2012普及组初赛试题答案C
【初中组kitten编程】2021NOC编程猫赛项—初赛模拟题模拟测试题附答案
百度之星试题,我也忘记是哪年的了。
2007年百度之星程序设计大赛复赛题目,应该可以帮助大家多了解一些大赛的出题规律
2011年百度之星程序设计大赛初赛A试题,有难度,有挑战性!!!
2011年百度之星程序设计大赛初赛B,经典的题目,挑战的趣味,还在等什么?
百度之星2009程序设计大赛 初赛第一场试题
2005年百度之星程序设计大赛试题初赛题 ,适合热爱Java人士
百度之星Astar2011程序设计大赛 初赛试题
对于2014年百度之星程序设计大赛迷宫问题的较为详尽的分析
百度之星2005-2007以及2011年的初赛复赛试题,文件为pdf文字版。