日本搞逼视频_黄色一级片免费在线观看_色99久久_性明星video另类hd_欧美77_综合在线视频

國內(nèi)最全IT社區(qū)平臺 聯(lián)系我們 | 收藏本站
阿里云優(yōu)惠2
您當(dāng)前位置:首頁 > php開源 > 綜合技術(shù) > 51nod-1091 . 線段的重疊

51nod-1091 . 線段的重疊

來源:程序員人生   發(fā)布時間:2014-09-29 20:27:14 閱讀次數(shù):3104次

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1091

題意:給定n條線段的起點和終點,計算線段的重疊部分,輸出最長的部分。沒有重疊就輸出0。

思路:最初思路 是用dp[i]保存前i個點線段重疊的最大部分,但是如果二維循環(huán),O(n*n)的復(fù)雜度,明顯超時,但是其實只用一維就完全可以搞定了,

先按起點排序?qū)λ悬c,然后找當(dāng)前點前面的所有線段終點最靠后的那根,就跟當(dāng)前線段有最大的重合,長度就是那個線段的終點減去當(dāng)前線段的起點,但是有一種情況就是那個線段的終點超過了當(dāng)前線段的終點,那么重合的長度就是當(dāng)前線段的長度,那根線段覆蓋當(dāng)前長度。只要每次保存最大值就行,這樣排序復(fù)雜度nlogn,一次遍歷n,總復(fù)雜度是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; }


 

 

生活不易,碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機掃描二維碼進行捐贈
程序員人生
------分隔線----------------------------
分享到:
------分隔線----------------------------
關(guān)閉
程序員人生
主站蜘蛛池模板: 国产精品二区一区二区aⅴ污介绍 | 成人自拍偷拍 | 国产成人精品视频 | 日韩三级在线播放 | www欧美 | 99精品国产高清在线观看 | 精品一区久久久 | 久久一| 国产在视频一区二区三区吞精 | 国产a一三三四区电影 | 欧美日韩视频一区二区三区 | 寡妇一级毛片视频 | 久久久综合色 | 久久999精品 | 精品视频免费在线 | 久久精品成人一区二区三区蜜臀 | 免费亚洲网站 | 精品亚洲一区二区 | 日本成人免费在线 | 精品久久中文 | 国产suv精品一区二区四 | 午夜av免费在线观看 | 久久久久久国产精品免费免费狐狸 | 99免费视频 | 91射区| 久久久久久免费毛片精品 | 亚洲欧美网站 | 一区二区三区四区日韩 | 成人午夜又粗又硬又大 | 久久国| 欧美日韩国产在线看 | 午夜毛片 | 一级片久久久久久 | 久久久久久久久成人 | 亚洲黄色免费看 | 日本在线免费播放 | 久久九九视频 | 中文字幕在线观看一区二区三区 | 欧美日韩精品一区二区三区四区 | 一级欧美黄色片 | 国产欧美日韩在线视频 |