lines

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

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
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

给你n条线段（点也算线段），让你找出被覆盖次数最多的线段的覆盖次数。

直接从左往右跑，线段起点加一过了减一。。。

官方题解：

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

题解：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #define mem(x,y) memset(x,y,sizeof(x))

 using namespace std;

 typedef long long LL;

 const int INF=0x3f3f3f3f;

 const int MAXN=1e5+;

 pair<int,int>pa[MAXN<<];

 int main(){

     int T,N;

     scanf("%d",&T);

     while(T--){int a,b;

         scanf("%d",&N);

         for(int i=;i<N;i++){

             scanf("%d%d",&a,&b);

             pa[i<<]=make_pair(a,);

             pa[i<<|]=make_pair(b+,-);

         }

         sort(pa,pa+N*);

         int ans=,cnt=;

         for(int i=;i<*N;i++)

             cnt+=pa[i].second,ans=max(ans,cnt);

         printf("%d\n",ans);

     }

     return ;

 }

巴特西

lines（最大区间和）

lines

最新文章

热门文章