首页 > 代码库 > BestCoder Round #20 lines (模拟线段树的思想)
BestCoder Round #20 lines (模拟线段树的思想)
lines
Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 787 Accepted Submission(s): 194
Problem Description
John has several lines. The lines are covered on the X axis. Let A is a point which is covered by the most lines. John wants to know how many lines cover A.
Input
The first line contains a single integer T(1≤T≤100)(the data for N>100 less than 11 cases),indicating the number of test cases.
Each test case begins with an integer N(1≤N≤105),indicating the number of lines.
Next N lines contains two integers Xi and Yi(1≤Xi≤Yi≤109),describing a line.
Each test case begins with an integer N(1≤N≤105),indicating the number of lines.
Next N lines contains two integers Xi and Yi(1≤Xi≤Yi≤109),describing a line.
Output
For each case, output an integer means how many lines cover A.
Sample Input
2
51
2 2
22
43
45
10005
1 1
2 2
3 3
4 4
5 5
Sample Output
31
题目意思很好懂,就是求n条线段的所覆盖的区域中,哪一个点被覆盖的次数最多。
一开始的思路是离散+线段树,因为这题和POJ 2528是同一个思路,只是求的值不同而已。
后来有一种思路,和线段树的思路很相近:
先把端点都存下来然后进行排序,这可以看成一个离散化处理。
如果在这个线段里面,b[左端点]++,b[右端点+1]--
这里可以用前缀和来解释这这种表示方法
比如一条线段的两个端点1 3
那么
b[1]=1, b[4]=-1;
b[1]=1 ,b[2]=b[1]+b[2]=1, b[3]=b[2]+b[3]=1, b[4]=b[3]+b[4]=0;
这样一来,问题就转化成了求前缀和的最大值是多少了。
#include<cstdio>#include<iostream>#include<cstring>#include<cmath>#include<stack>#include<queue>#include<stack>#include<stdlib.h>#include<algorithm>#define LL __int64using namespace std;const double EPS=1e-8;const int MAXN=100000+5;int a[MAXN*2],b[MAXN*2];struct node{ int star,en;}line[MAXN];int bs(int a[],int x,int val){ int l=0,r=x-1; while(l<=r) { int mid=(l+r)/2; if(a[mid]==val) return mid; if(val>a[mid]) l=mid+1; else r=mid-1; }}int main(){ int kase,n; scanf("%d",&kase); while(kase--) { int cnt=0; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d %d",&line[i].star,&line[i].en); a[cnt++]=line[i].star; a[cnt++]=line[i].en; //将端点记录在a数组中 } sort(a,a+cnt); //排序的话,可以说是一个离散化处理 int p=1; for(int i=1;i<cnt;i++) if(a[i]!=a[i-1]) a[p++]=a[i]; //删除重复的端点 for(int i=0;i<n;i++) { int vis; vis=bs(a,p,line[i].star); b[vis]++; vis=bs(a,p,line[i].en); b[vis+1]--; } int maxn=b[0]; for(int i=1;i<p;i++) { b[i]=b[i-1]+b[i]; if(b[i]>maxn) maxn=b[i]; } printf("%d\n",maxn); } return 0;}
BestCoder Round #20 lines (模拟线段树的思想)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。