hdu 5124 lines【转化为区间和】

本文主要是介绍hdu 5124 lines【转化为区间和】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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)T(1≤T≤100)(the data for N>100N>100 less than 11 cases),indicating the number of test cases. 
Each test case begins with an integer N(1≤N≤105)N(1≤N≤105),indicating the number of lines. 
Next N lines contains two integers XiXi and Yi(1≤Xi≤Yi≤109)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

题意：

      在X轴上面，输入n条线段的左右端点，求覆盖次数最多的点的次数。

分析：

      离散化那种方式个人感觉不是很好懂，就看了转化为区间和 的方法。

      官方题解：（我就不罗嗦了）

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

        一开始我也没看太懂自己手动模拟一下样例就能明白了。

代码：

 

#include<cstdio>
#include<utility>
#include<algorithm>
#include<cstring>
using namespace std;
typedef pair<int,int> p;
p a[200008];
int main()
{int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);n*=2;for(int i=0;i<n;i++){scanf("%d",&a[i].first);a[i].second=1;scanf("%d",&a[++i].first);a[i].first++;///坐标后移1位a[i].second=-1;}sort(a,a+n);///pair默认对第一个元素升序排序int ans=0,k=0;for(int i=0;i<n;i++){k+=a[i].second;ans=max(ans,k);}printf("%d\n",ans);}return 0;
}

 

 

 

 

这篇关于hdu 5124 lines【转化为区间和】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---