本文主要是介绍astar 集合的交与并，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
C:集合的交与并
- 时间限制:
- 1000ms 内存限制:
- 65536kB
- 描述
-
对于一个闭区间集合{A1,A2……AK}(K>1，Ai<>Aj{i<>j})，我们定义其权值
W=|A1∪A2∪……∪AK|*|A1∩A2∩……AK|
其中|X|表示X区间的长度；如果X为空集|X|=0。
当然，如果这些闭区间没有交集则权值为0。
给定N个各不相同的闭区间，请你从中找出若干个(至少2个)区间使其权值最大。
输入 - 第一行一个整数N (2 <= N <= 10^5)
接下来N行每行两个整数 l r(1 <= l <= r <= 10^6)，表示闭区间的两个端点。 输出 - 最大权值 样例输入
-
4
-
1 6
-
4 8
-
2 7
-
3 5
样例输出 -
24
这题是astar的题，表示不知道怎么搞，时间复查度是n =10^5 ，必须要至少 O（n*log n）的时间复查度 ，我的的思路是先把每段区间按左端点 由大到小排序，然后再右断电排，最后像最大字段和那么dp下就可以了…纯属于个人yy的，也不知道对不对，更不会证明……
很戳的代码：有时间在瞅瞅
#include <cstdlib>
#include <iostream>using namespace std;
struct Node
{int l,r;
}line[100010];int cmp(Node a,Node b)
{if(a.l!=b.l) return a.l < b.l;return a.r < b.r;
}
int main(int argc, char *argv[])
{int n,l,r;while(scanf("%d",&n)==1){for(int i=0;i<n;i++) scanf("%d %d",&line[i].l,&line[i].r);sort(line,line+n,cmp);int ans=0,a,b,start;l=line[0].l,r=line[0].r,start=line[0].l;for(int i=1;i<n;i++){a=line[i].l,b=line[i].r;if(a>=r) l=a,r=b,start=a;else{if(b<=r){if(ans<=(r-start)*(b-a)) ans=(r-start)*(b-a),l=a,r=b;else l=a,r=b,start=a;}else{if(ans<=(b-start)*(r-a)) ans=(b-start)*(r-a),l=a;else l=a,r=b,start=a;}}}printf("%d\n",ans);}// system("PAUSE");return EXIT_SUCCESS;
}
这篇关于astar 集合的交与并的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
