本文主要是介绍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【转化为区间和】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
