Mayor's posters POJ2528 ACM算法設計 -开发者知识库

Mayor's posters POJ2528 ACM算法設計 -开发者知识库,第1张

題目鏈接:http://poj.org/problem?id=2528

大致題意:

有一面牆,被等分為1千萬份,一份的寬度為一個單位寬度。現在往牆上貼N張海報,每張海報的寬度是任意的,但是必定是單位寬度的整數倍,且<=1QW。后貼的海報若與先貼的海報有交集,后貼的海報必定會全部或局部覆蓋先貼的海報。現在給出每張海報所貼的位置(左端位置和右端位置),問張貼完N張海報后,還能看見多少張海報

注意:

這面牆被分為1千萬份,從1開始對每份命名,就是說,如果海報的起、終為5 5 ,則海報占據了第5個單元格,若為5 6,則占據了第5和第6個單元格。

錯誤的離散化:

如這組數據

1
3
1 10
1 3
6 10

不離散的話,正確答案是3,錯誤離散后答案成了2.

下面是沒AC的代碼,紀念逝去的10 個小時..

  1 #include <iostream>
  2 #include <algorithm>
  3 #include <string.h>
  4 //#include <fstream>
  5 using namespace std;
  6 
  7 struct LineTreeNode
  8 {
  9     int l,r,col;
 10 };
 11 const unsigned int MAXnumber = (unsigned int)1e7;
 12 const int MAXposters = 10000;
 13 unsigned int posters[MAXposters 1][2];
 14 unsigned int mapping[MAXnumber 1];
 15 unsigned int posterPoints[MAXposters*2 1];
 16 bool IsAdded[MAXposters 1];
 17 LineTreeNode LT[MAXposters*2*4 1];
 18 int posterCount;
 19 unsigned int lineTreeLength;
 20 int ans;
 21 
 22 void creatTree(const int& l,const int& r,const int& p)
 23 {
 24     LT[p].l = l;
 25     LT[p].r = r;
 26     if(l == r)
 27         return;
 28     int mid = (l   r) >> 1;
 29     creatTree(l,mid,p * 2);
 30     creatTree(mid   1,r,p * 2   1);
 31 }
 32 void insertVal(const int& l,const int& r,const int& p,const int& col)
 33 {
 34     if(l > LT[p].r || r < LT[p].l)
 35         return;
 36     if(l <= LT[p].l && r >= LT[p].r)
 37     {
 38         LT[p].col = col;
 39         return;
 40     }
 41     if(LT[p].col >=  0)
 42     {
 43         LT[p*2].col = LT[p*2   1].col = LT[p].col;
 44         LT[p].col = -1;
 45     }
 46     insertVal(l,r,p*2,col);
 47     insertVal(l,r,p*2 1,col);
 48 }
 49 void dfsSearch(const int& p)
 50 {
 51     if(LT[p].col > 0 && !IsAdded[LT[p].col])
 52     {
 53         ans  ;
 54         IsAdded[LT[p].col] = true;        
 55         return;
 56     }
 57     if(LT[p].col == 0 || LT[p].l == LT[p].r)
 58         return;    
 59     dfsSearch(p*2);
 60     dfsSearch(p*2 1);        
 61 }
 62 int main()
 63 {
 64     //ifstream cin("in.txt");
 65     int cases;
 66     cin>>cases;
 67     while (cases --)
 68     {            
 69         cin>>posterCount;
 70         //Init
 71         ans = 0;
 72         lineTreeLength = 0;
 73         memset(IsAdded,false,sizeof(IsAdded));
 74         memset(mapping,0,sizeof(mapping));
 75         memset(posterPoints,0,sizeof(posterPoints));
 76         for(int i = 1;i < posterCount * 2 * 4   1;i   )
 77             LT[i].l = LT[i].r = LT[i].col = 0;
 78         //Input    
 79         int p = 0;
 80         for(int i = 1;i <= posterCount;i  )
 81         {
 82             cin>>posters[i][0]>>posters[i][1];
 83             if(!mapping[posters[i][0]])
 84             {
 85                 posterPoints[p  ] = posters[i][0];
 86                 mapping[posters[i][0]] = 1;
 87             }
 88             if(!mapping[posters[i][1]])
 89             {
 90                 posterPoints[p  ] = posters[i][1];
 91                 mapping[posters[i][1]] = 1;
 92             }
 93         }
 94         //Sort
 95         sort(posterPoints,posterPoints   p);
 96         //Map
 97         for(int i = 0;i < p;i   )
 98         {
 99             mapping[posterPoints[i]] =   lineTreeLength;
100         }
101         //Construct LineTree
102         creatTree(1,lineTreeLength,1);
103         //Place posters
104         for(int i = 1;i <= posterCount;i   )
105             insertVal(mapping[posters[i][0]],mapping[posters[i][1]],1,i);
106         //How much can we see
107         dfsSearch(1);
108         //Print
109         cout<<ans<<endl;
110     }
111 }

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复