51nod-1091 . 線段的重疊
來源:程序員人生 發布時間:2014-09-29 20:27:14 閱讀次數:3099次
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1091
題意:給定n條線段的起點和終點,計算線段的重疊部分,輸出最長的部分。沒有重疊就輸出0。
思路:最初思路 是用dp[i]保存前i個點線段重疊的最大部分,但是如果二維循環,O(n*n)的復雜度,明顯超時,但是其實只用一維就完全可以搞定了,
先按起點排序對所有點,然后找當前點前面的所有線段終點最靠后的那根,就跟當前線段有最大的重合,長度就是那個線段的終點減去當前線段的起點,但是有一種情況就是那個線段的終點超過了當前線段的終點,那么重合的長度就是當前線段的長度,那根線段覆蓋當前長度。只要每次保存最大值就行,這樣排序復雜度nlogn,一次遍歷n,總復雜度是nlogn。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
int x,y;
}p[50001];
int cmp(node a,node b)
{
if(a.x!=b.x) return a.x<b.x;
else return a.y<b.y;
}
int main()
{
//freopen("a.txt","r",stdin);
int n,i,j,maxn=0;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d%d",&p[i].x,&p[i].y);
sort(p,p+n,cmp);
int m=p[0].y;
for(i=1;i<n;i++)
{
if(p[i].y>=m) { maxn=max(maxn,m-p[i].x); m=p[i].y;}
else maxn=max(maxn,p[i].y-p[i].x);
}
printf("%d
",maxn);
return 0;
}
生活不易,碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈