首页 > 代码库 > HDU 5124 lines 最多区间覆盖

HDU 5124 lines 最多区间覆盖

点击打开链接

lines

Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 453    Accepted Submission(s): 220


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(1T100)(the data for N>100 less than 11 cases),indicating the number of test cases.
Each test case begins with an integer N(1N105),indicating the number of lines.
Next N lines contains two integers Xi and Yi(1XiYi109),describing a line.
 

Output
For each case, output an integer means how many lines cover A.
 

Sample Input
2 5 1 2 2 2 2 4 3 4 5 1000 5 1 1 2 2 3 3 4 4 5 5
 

Sample Output
3 1
 

Source
BestCoder Round #20
 
官方题解:
我们可以将一条线段[xi,yi]分为两个端点xi(yi)+1,在xi时该点会新加入一条线段,同样的,在(yi)+1时该点会减少一条线段,因此对于2n个端点进行排序,令xi为价值1,yi为价值-1,问题转化成了最大区间和,因为1一定在-1之前,因此问题变成最大前缀和,我们寻找最大值就是答案,另外的,这题可以用离散化后线段树来做。复杂度为排序的复杂度即nlgn,另外如果用第一种做法数组应是2n,而不是n,由于各种非确定性因素我在小数据就已经设了n=10W的点。
//953MS	1792K
#include<stdio.h>
#include<algorithm>
using namespace std;
pair<int,int>p[200007];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,a,b;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%d%d",&a,&b);
            p[i*2]=make_pair(a,1);
            p[i*2+1]=make_pair(b+1,-1);
        }
        sort(p,p+2*n);//对坐标进行排序
        int ans=0,maxx=0;
        for(int i=0;i<2*n;i++)
        {
            ans+=p[i].second;
            if(ans>maxx)maxx=ans;
        }
        printf("%d\n",maxx);
    }
    return 0;
}


HDU 5124 lines 最多区间覆盖