【2012百度之星/初赛上】C:集合的交与并

对于一个闭区间集合{A₁,A₂……A_K}(K>1，A_i≠A_j{i≠j})，我们定义其权值

其中|X|表示X区间的长度；如果X为空集|X|=0。

当然，如果这些闭区间没有交集则权值为0。

给定N个各不相同的闭区间，请你从中找出若干个(至少2个)区间使其权值最大。

输入

第一行一个整数N (2 <= N <= 10⁵)

接下来N行每行两个整数 l r(1<=l<=r<=10⁶)，表示闭区间的两个端点。

输出

最大权值

样例输入

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;elsereturn 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百度之星/初赛上】C:集合的交与并的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。