HOJ 2278

主要思路：將IP地址看成4位256進制的數，轉化成十進制，一個segment就是一個區間。

先將所有的segment按左端點升序排列，如果幾個segment有重疊，則將它們合并成一個區間。

int dn=0;l=seg[0].start;r=seg[0].end;for(int j=1;j<i;j++){if(seg[j].start<=r){r=max(seg[j].end,r);continue;}seg[dn].start=l;seg[dn].end=r;dn++;l=seg[j].start;r=seg[j].end;}seg[dn].start=l;seg[dn].end=r;dn++;

?

這樣結束之后，可以獲得幾個沒有公共區域的區間。

接下來可以對segment的下標進行二分了。

如果seg[i].start>target,說明target落在了有效區間的左邊，此時應該取二分的上半區域，即low=mid+1

同理，如果seg[i].end<target,此時應該high=mid-1;

? ? ?

low=0;high=dn-1;while (low <= high){mid = (high + low) / 2;if(temp>=seg[mid].start&&temp<=seg[mid].end){flag=1;break;}if (seg[mid].start>temp){high = mid-1 ;}else if(seg[mid].end<temp){low = mid + 1;}}

?

這樣最終如果能找到一個區間seg[mid]，使target在這個區間內，輸出yes，若low>high之后仍然沒有找到這樣的區間，說明target不在任何一個區間內，輸出no.

總的來說是挺簡單的一道二分，卻卡了很長時間。總是在各種細節上出錯，顧此失彼。說明練習不足，碼力不夠，容易犯迷糊。

轉載于:https://www.cnblogs.com/MicZ/archive/2012/08/24/2785380.html

總結

以上是生活随笔為你收集整理的HOJ 2278 IP Filtering (二分)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。