【POJ2528】Mayor's posters ||【NYOJ9】 (线段树)

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 04 月 12 日

北大poj这题测试数据有错,离散化错误,请到这里提交http://acm.nyist.net/JudgeOnline/problem.php?pid=9测试你的程序。

代码注释比较详细,不再赘述

 /*为大家方便明白,注释比较多。该题可学会线段树简单用法,学会数据的离散化,还是一个不错的题。*/  
#include<iostream>  
#include<algorithm>  
using namespace std;  
#define maxnum 20005  
//定义海报结构体并声明相应空间,order 粘贴顺序pos表示两边位置  
struct post  
{  
    int order;  
    int pos;  
}poster[maxnum];  
//定义建树结构体并声明一个数组树,l 孩子边界 r孩子右边界vis 是否访问过  
struct{  
    int l, r;  
    bool vis;  
}node[20*maxnum];//粗略估计建树所需节点数。  
bool flag;  
//按海报位置排序用,用于离散化数据  
bool cmp1(post p1,post p2)  
{return p1.pos<p2.pos;}  
//按海报粘贴顺序排序用,用于查询树  
bool cmp2(post p1,post p2)  
{  
    if(p1.order>p2.order) return true;  
    else if(p1.order==p2.order) return p1.pos<p2.pos;  
    return false;  
}  
//用数组模拟二叉树建树u 为树的相应节点,注意:该方法适用只适用固定个数子树的树。  
void BuildTree(int left, int right, int u){         
    node[u].l = left;  
    node[u].r = right;  
    node[u].vis = false;  
    if(left == right) return;  
    int mid = (left+right)>>1; //曾经周五讲课给大家说过,右移为除2操作  
    BuildTree(left, mid, u<<1); //左移为乘2操作  
    BuildTree(mid+1, right, (u<<1)+1);  
}  
//查询  
void query(int left, int right, int u){            
    if(node[u].vis == true) return;  
    if(node[u].l == left && node[u].r == right){  
        node[u].vis = true;       //  修改。  
        flag = true;              //  对于新帖的海报,有区间可以让其露出来。  
        return;  
    }  
    if(right <= node[u<<1].r)  
        query(left, right, u<<1);  
    else if(left >= node[(u<<1)+1].l)  
        query(left, right, (u<<1)+1);  
    else{  
        query(left, node[u<<1].r, u<<1);  
        query(node[(u<<1)+1].l, right, (u<<1)+1);  
    }  
    //递归回来的时候,由于左右子结点性质的改变,必须对父结点信息进行相应的更改。  
    node[u].vis = node[u<<1].vis & node[(u<<1)+1].vis;  
}  
int main()  
{  
    freopen("1.txt","r",stdin);  
    freopen("2.txt","w",stdout);  
    int n,m,sum;  
    cin>>n;  
    while(n--)  
    {  
        sum=0;  
        cin>>m;  
        for (int i=0;i<m;i++)  
        {  
            cin>>poster[2*i].pos>>poster[2*i+1].pos;  
            poster[2*i].order=poster[2*i+1].order=i;  
        }  
/*  以下进行离散化,同样的上次周五讲课有跟大家讲到,这里再次详细举例: 
 *  例如有一组数:10000 -100 100  100 500 2000  这些数的大小如果对我们来说并无太大意义, 
 *  或者我们并不关心其大小,我们可以对其进行排序,然后根据每个数的位置进行相应的离散化 
 *  如:排序后-100 100 100 500 2000 10000  离散化后:2 2 3 4 5。这样我们就把范围在-100到 
 *  的数据离散化到范围为到的数据。用于该题可大大缩减建树所需规模。 
 */  
        sort(poster,poster+2*m,cmp1);  
        int index=0,pre=-1;  
        for (int i=0;i<2*m;i++)  
        {  
            if(poster[i].pos !=pre && poster[i].pos !=pre+1)  
            {  
                pre=poster[i].pos;  
                ++index;  
                poster[i].pos =++index;  
            }else if(poster[i].pos !=pre)  
            {  
                pre=poster[i].pos;  
                poster[i].pos =++index;  
            }  
            else poster[i].pos=index;  
        }  
        //按粘贴顺序排序,从最后向前查询是否可见。  
        sort(poster,poster+2*m,cmp2);  
        BuildTree(1,index, 1);  
        for (int i=0;i<2*m;i+=2)  
        {  
            flag=false;  
            query(poster[i].pos,poster[i+1].pos,1);  
            if(flag) sum++;  
        }  
        cout<<sum<<endl;  
    }  
}  

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期五, 2017 年 12 月 15 日