首页 > 代码库 > POJ 2528 (线段树+离散化) Mayor's posters

POJ 2528 (线段树+离散化) Mayor's posters

2024-07-16 13:57:42   229人阅读

因为将每个单位都作为一个最小单元的话会爆内存的

所以，将海报的每个端点进行排序，将这些端点最为最小的区间。

毕竟是刚刚接触线段树，理解起来还有些吃力，还是那句话，题做多了慢慢就好了。

 

萌萌的AC代码君贴上。

  1 //#define LOCAL  2 #include <iostream>  3 #include <algorithm>  4 #include <cmath>  5 using namespace std;  6   7 int n;  8 struct CPost  9 { 10     int L, R; 11 }posters[10000 + 100]; 12 int x[20000 + 200];    //海报的端点瓷砖编号 13 int hash[10000000 + 10];//hash[i]表示瓷砖i所处的离散化后的区间编号 14  15 struct CNode 16 { 17     int L, R; 18     bool bCovered;    //区间[L, R]是否已经完全覆盖 19     CNode *pLeft, *pRight; 20 }Tree[1000000]; 21 int nNodeCount = 0; 22 int Mid(CNode* pRoot) 23 { 24     return (pRoot->L + pRoot->R) / 2; 25 } 26 void BuildTree(CNode *pRoot, int L, int R) 27 { 28     pRoot->L = L; 29     pRoot->R = R; 30     pRoot->bCovered = false; 31     if(L == R) 32         return; 33     ++nNodeCount; 34     pRoot->pLeft = Tree + nNodeCount; 35     ++nNodeCount; 36     pRoot->pRight = Tree + nNodeCount; 37     BuildTree(pRoot->pLeft, L, (L+R)/2); 38     BuildTree(pRoot->pRight, (L+R)/2+1, R); 39 } 40 bool Post(CNode *pRoot, int L, int R) 41 {//插入一张覆盖区间[L, R]的海报，返回true则说明该区间是部分或者全部可见的 42     if(pRoot->bCovered) 43         return false; 44     if(pRoot->L == L && pRoot->R == R) 45     { 46         pRoot->bCovered = true; 47         return true; 48     } 49     bool bResult; 50     if(R <= Mid(pRoot)) 51         bResult = Post(pRoot->pLeft, L, R); 52     else if(L >= Mid(pRoot) + 1) 53         bResult = Post(pRoot->pRight, L, R); 54     else 55     { 56         bool b1 = Post(pRoot->pLeft, L, Mid(pRoot)); 57         bool b2 = Post(pRoot->pRight, Mid(pRoot) + 1, R); 58         bResult = b1 || b2; 59     } 60     //要更新的节点的覆盖情况 61     if(pRoot->pLeft->bCovered && pRoot->pRight->bCovered) 62         pRoot->bCovered = true; 63     return bResult; 64 } 65  66 int main(void) 67 { 68     #ifdef LOCAL 69         freopen("2528in.txt", "r", stdin); 70     #endif 71     int t; 72     int i, j, k; 73     scanf("%d", &t); 74     int nCaseNo = 0; 75     while(t--) 76     { 77         ++nCaseNo; 78         scanf("%d", &n); 79         int nCount = 0; 80         for(i = 0; i < n; ++i) 81         { 82             scanf("%d%d", &posters[i].L, &posters[i].R); 83             x[nCount++] = posters[i].L; 84             x[nCount++] = posters[i].R; 85         } 86         sort(x, x + nCount); 87         nCount = unique(x, x + nCount) - x;//元素去重 88         //将下面离散化 89         int nIntervalNo = 0; 90         for(i = 0; i < nCount; ++i) 91         { 92             hash[x[i]] = nIntervalNo; 93             if(i < nCount - 1) 94             { 95                 if(x[i + 1] - x[i] == 1) 96                     ++nIntervalNo; 97                 else 98                     nIntervalNo += 2; 99             }100         }101 102         BuildTree(Tree, 0, nIntervalNo);103         int nSum = 0;104         for(i = n - 1; i >= 0; --i)105         {//从后往前遍历每个海报是否可见106             if(Post(Tree, hash[posters[i].L], hash[posters[i].R]))107                 ++nSum;108         }109         printf("%d\n", nSum);110     }111     return 0;112 }
代码君

 


联系
我们