題目：Mayor's posters

?

首先本題題意是：有一面墻，被等分為1QW份，一份的寬度為一個單位寬度。現在往墻上貼N張海報，每張海報的寬度是任意

的，但是必定是單位寬度的整數倍，且<=1QW。后貼的海報若與先貼的海報有交集，后貼的海報必定會全部或局部覆蓋先貼的海

報。現在給出每張海報所貼的位置（左端位置和右端位置），問張貼完N張海報后，還能看見多少張海報？

?

利用線段切割，由于后貼的海報可能會覆蓋前面的，而很明顯知道前面的海報不會影響后面海報的可見性，所以應該從后面往

前面推。

?

所以程序中就有：for(i=n-1;i>=0;i--)???

現在我們暫時只分析前一張海報與后一張海報的關系就可以了，然后遞推就可以了。

我們用海報的長度來表示可見性，如果長度大于0，當然就可見啊

對于海報之間的關系，只有那么幾種情況，但是看程序中只有3種關系，實際上在統計可見性時我們說只需要3種就夠了，為什

么呢？

?

我們可以自己模擬一下：

如果兩張海報沒有交集，那么下面的那張海報一定是可見的，所以長度當然大于0，

如果兩張海報有交集，就必然有4種關系，但是這里我們相當于只有兩種就夠了，就是后面的覆蓋前面的右半部分，或者后面的

覆蓋前面的左半部分，注意我們開始memset所有的海報長度是0，所以如果出現后面的海報全部覆蓋前面的海報的情況就不用

管，因為它就是0，但是還有一種關系，就是后面的海報覆蓋前面海報的中間部分，這樣的話我們就可以把它當成覆蓋左邊部分

或者覆蓋右邊部分，因為我們的判斷語句是

?if(l<node[k].x)?

?if(r>node[k].y)???

很明顯可以看出實際上這兩個語句包含了3種情況。而不僅僅代表只覆蓋右部分或者左部分。

這樣我們在結構體里面用ans統計每張海報最終的長度，實際上不一定是真正的長度哈，比如后一張只覆蓋前一張的和中間部分

的那一種情況，實際上ans就只記錄了前面的海報的左邊部分，所以這樣本題就解決了，線段切割實現起來更容易。

注意線段切割與矩形切割適用的范圍：對邊界范圍大，操作數少的題目，我們選擇矩形切割或者線段切割。?

#include <stdio.h> #include <string.h>const int N = 10005;typedef struct {int x,y;int ans; }Node;Node node[N];int n;void Cover(int l,int r,int k,int c) {while(k<n&&(r<node[k].x||l>node[k].y)) k++;if(k>=n) //當前進行切割的線段并沒有和后面的線段相交{node[c].ans+=r-l+1;return;}if(l<node[k].x) Cover(l,node[k].x-1,k+1,c); //當前線段的右邊被覆蓋；if(r>node[k].y) Cover(node[k].y+1,r,k+1,c); //當前線段的左邊被覆蓋； }int main() {int t,i,sum;scanf("%d",&t);while(t--){sum=0;memset(node,0,sizeof(node));scanf("%d",&n);for(i=0;i<n;i++)scanf("%d%d",&node[i].x,&node[i].y);for(i=n-1;i>=0;i--) //這里是用后面的海報覆蓋前面的海報，所以要從后面開始進行插入（進行線段切割）；Cover(node[i].x,node[i].y,i+1,i);for(i=0;i<n;i++)if(node[i].ans>0)sum++;printf("%d\n",sum);}return 0; }

?

?

總結

以上是生活随笔為你收集整理的POJ2528的另一种解法(线段切割)的全部內容，希望文章能夠幫你解決所遇到的問題。

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