程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ-2528-Mayors posters

POJ-2528-Mayors posters

編輯:C++入門知識

線段樹的離散化,離散化就相當於是先做映射,然後再建樹

對於題目給出的測試數據

1 4

2 6

8 10

3 4

7 10

將端點取出並且排序,去掉相同的坐標,即1,2,3,4,6,7,8,10,那麼

1,2,3,4,6,7,8,10可以離散化為

1,,2,3,4,5,6,7,8

題目給出的區間可以表示為

1 4

2 5

7 8

3 4

6 8

這樣會減小建樹的空間


[cpp] 
#include<iostream> 
#include<cstdio> 
#include<cstring> 
#include<cstdlib> 
#include<algorithm> 
using namespace std; 
#define Max 10010 
struct cam1 

    int l,r; 
}post[Max]; 
int x[Max*2];//坐標 
int h[10000005]; 
struct cam2 

    int l,r; 
    int flag;  //標記是否被覆蓋 
}list[Max*8]; 
int cmp(const void *a,const void *b) 

    return *(int *)a-*(int *)b; 

void build(int k,int l,int r) 

    list[k].l=l; 
    list[k].r=r; 
    list[k].flag=0; 
    if(l==r) 
    return; 
    int mid=(l+r)/2; 
    build(k<<1,l,mid); 
    build(k<<1|1,mid+1,r); 

int query(int k,int l,int r) 

    if(list[k].flag) 
    return 0; 
    if(list[k].l==l&&list[k].r==r) 
    { 
        list[k].flag=1; 
        return 1; 
    } 
    int result,mid; 
    mid=(list[k].l+list[k].r)/2; 
    if(r<=mid) 
    result=query(k<<1,l,r); 
    else if(l>mid) 
    result=query(k<<1|1,l,r); 
    else 
    result=query(k<<1,l,mid)|query(k<<1|1,mid+1,r); 
    if(list[k<<1].flag&&list[k<<1|1].flag)  //孩子節點反饋給父親結點 
    list[k].flag=1; 
    return result; 

int main() 

    int t,cnt; 
    int i,j,k,n,ans; 
    scanf("%d",&t); 
    while(t--) 
    { 
        scanf("%d",&n); 
        cnt=0; 
        for(i=0;i<n;i++) 
        { 
            scanf("%d%d",&post[i].l,&post[i].r); 
            x[cnt++]=post[i].l; 
            x[cnt++]=post[i].r; 
        } 
        sort(x,x+cnt);//從小到大排序 
        cnt=unique(x,x+cnt)-x; //消除相同的坐標 
        for(i=0;i<cnt;i++) 
        h[x[i]]=i; 
        build(1,0,cnt-1); 
        ans=0; 
        for(i=n-1;i>=0;i--) 
        if(query(1,h[post[i].l],h[post[i].r])) 
        ans++;  www.2cto.com
        printf("%d\n",ans); 
    } 
    return 0; 


作者:Cambridgeacm

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved