首页 > 代码库 > BestCoder Round #20 lines (模拟线段树的思想)

BestCoder Round #20 lines (模拟线段树的思想)

2024-08-05 10:50:37   218人阅读

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.
 
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;}
View Code

 

 

BestCoder Round #20 lines (模拟线段树的思想)


联系
我们