首页 > 代码库 > hdu 5124 lines
hdu 5124 lines
http://acm.hdu.edu.cn/showproblem.php?pid=5124
题意：给你n条线段，然后找出一个被最多条线段覆盖的点，输出覆盖这个点的线段的条数。
思路：可以把一条线段分出两个端点离散化，左端点被标记为-1，右端点被标记为1，然后排序，如果遇到标记为-1，cnt++，否则cnt--;找出cnt的最大值。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 200010 5 using namespace std; 6 7 struct node 8 { 9 int x,c;10 bool operator<(const node &a)const11 {12 return (x<a.x)||(x==a.x&&c<a.c);13 }14 }p[maxn];15 16 int t;17 int n;18 19 int main()20 {21 scanf("%d",&t);22 while(t--)23 {24 scanf("%d",&n);25 for(int i=0; i<n; i++)26 {27 int s,e;28 scanf("%d%d",&s,&e);29 p[i*2].x=s;30 p[i*2].c=-1;31 p[i*2+1].x=e;32 p[i*2+1].c=1;33 }34 sort(p,p+2*n);35 int cnt=0; int ans=0;36 for(int i=0; i<2*n; i++)37 {38 if(p[i].c==-1)39 {40 cnt++;41 }42 else43 cnt--;44 ans=max(ans,cnt);45 }46 printf("%d\n",ans);47 }48 return 0;49 }
hdu 5124 lines
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。