首页 > 代码库 > 【扫描线】HDU 5124 lines
【扫描线】HDU 5124 lines
http://acm.hdu.edu.cn/showproblem.php?pid=5124
【题意】
在数轴x上,每次操作都覆盖一个区间的所有点,问被覆盖次数最多的点是覆盖了多少次
【思路】
最简单的扫描线,左右端点分别排序,遇到左端点sum++更新最值,遇到右端点sun--更新最值
【Accepted】
1 #include<bits/stdc++.h> 2 using namespace std; 3 int a[100010],b[100010]; 4 int t,n; 5 bool cmp(int aa,int bb) 6 { 7 return aa<bb; 8 } 9 int main() 10 { 11 scanf("%d",&t); 12 while(t--) 13 { 14 scanf("%d",&n); 15 for(int i=0; i<n; i++) 16 scanf("%d%d",&a[i],&b[i]); 17 sort(a,a+n,cmp); 18 sort(b,b+n,cmp); 19 int maxx=0,sum=0; 20 int j=0,i=0; 21 while(i!=n && j!=n) 22 { 23 if(b[j]<a[i]) 24 { 25 sum--; 26 j++; 27 } 28 else 29 { 30 sum++; 31 i++; 32 } 33 maxx=max(maxx,sum); 34 //printf("%d\n",maxx); 35 } 36 printf("%d\n",maxx); 37 } 38 return 0; 39 }
【扫描线】HDU 5124 lines
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。