51node1091 线段的最长交集（贪心） 男娘i 2022-08-21 12:48 137阅读 0赞 X轴上有N条线段，每条线段包括1个起点和终点。线段的重叠是这样来算的，\[10 20\]和\[12 25\]的重叠部分为\[12 20\]。 给出N条线段的起点和终点，从中选出2条线段，这两条线段的重叠部分是最长的。输出这个最长的距离。如果没有重叠，输出0。 排序之后直接贪心就可以了。 #include <cstdio> #include <cmath> #include <iostream> #include <algorithm> using namespace std; int const maxn = 50005 ; struct node { long long l,r; }A[maxn]; bool cmp(node a,node b) { if(a.l!=b.l)return a.l<b.l; return a.r<b.r; } int main() { int n ; while(scanf("%d",&n)!=EOF) { for(int i = 0 ; i < n ; i++) { scanf("%I64d%I64d",&A[i].l,&A[i].r); } sort(A,A+n,cmp); long long ans = 0 ; long long maxx = A[0].r ; for(int i = 1 ; i < n ; i++) { if(A[i].l<=maxx) { ans = max(ans,min(maxx,A[i].r)-A[i].l); } //cout<<ans<<endl; maxx = max(A[i].r,maxx); } printf("%I64d\n",ans); } return 0; }
还没有评论，来说两句吧...