首页 > 代码库 > 5124 lines

5124 lines

2024-08-06 05:34:47   217人阅读

· 题意： 给n条线段，求某点上最多覆盖多少条线段。

·hdu上有题解：

1002 lines我们可以将一条线段[xi,yi]分为两个端点xi和(yi)+1，在xi时该点会新加入一条线段，同样的，在(yi)+1时该点会减少一条线段，因此对于2n个端点进行排序，令xi为价值1，yi为价值-1，问题转化成了最大区间和，因为1一定在-1之前，因此问题变成最大前缀和，我们寻找最大值就是答案，另外的，这题可以用离散化后线段树来做。复杂度为排序的复杂度即nlgn，另外如果用第一种做法数组应是2n，而不是n，由于各种非确定性因素我在小数据就已经设了n=10W的点。

·排序一开始写成了sort(f,f+n,cmd);  其中n忘了乘2，WA了一发。。。

 1 #include <iostream> 2 #include <stdio.h> 3 #include <algorithm> 4 #include <cstring> 5 #include <string.h> 6 #include <math.h> 7 #include <queue> 8 #include <stack> 9 #include <stdlib.h>10 #include <map>11 using namespace std;12 #define LL long long13 #define sf(a) scanf("%d",&(a));14 #define N 50001015 16 struct LNode{17     int x,flag;18 }f[N];19 int cmd(struct LNode x,struct LNode y){20     if(x.x==y.x) return x.flag>y.flag;21     return x.x<y.x;22 }23 int main()24 {25     int n,t;26     scanf("%d",&t);27     while(t--){28         //memset(f,0,sizeof(f));29         scanf("%d",&n);30         for(int i=0;i<2*n;i=i+2) {31             int x,y;32             scanf("%d %d",&x,&y);33             f[i].x=x;f[i].flag=1;34             f[i+1].x=y+1;f[i+1].flag=2;35         }36         sort(f,f+2*n,cmd);37         int maxc=-1;int num=0;38         for(int i=0;i<n*2;i++){39             if(f[i].flag==1) num++;40             else num--;41             if(num > maxc) maxc = num;42         }43         printf("%d\n",maxc);44     }45 46     return 0;47 }

 

5124 lines


联系
我们