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

简介:
+关注继续查看

/*
poj 2528 Mayor's posters 
线段树 + 离散化

离散化的理解:
  给你一系列的正整数, 例如 1, 4 , 100, 1000000000, 如果利用线段树求解的话,很明显
  会导致内存的耗尽。所以我们做一个映射关系,将范围很大的数据映射到范围很小的数据上
  1---->1  4----->2  100----->3  1000000000----->4
  这样就会减少内存一些不必要的消耗 
  建立好映射关系了,接着就是利用线段树求解 
*/ 
#include<iostream> 
#include<cstdio>
#include<queue> 
#include<cstring>
#include<algorithm>
#define N 10000010
#define M 10005
using namespace std;
class EDGE{
public: 
   int ld, rd;
};
int tree[M*16];//一共有M*2个端点,一个线段映射到四个点,左右端点, 左端点-1, 右端点+1, 数组的大小是线段树最底层数据个数的4倍 
EDGE edge[M];
int p[M*4];
int hash[N];
int n;

int insert(int p, int lr, int rr, int ld, int rd){
    
    if(tree[p] && lr<=ld && rd<=rr)//如果当前的区间[ld, rd]被包含在[lr, rr]中,而且[lr, rr]的区间已经被覆盖 
       return 1;
    else if(lr==ld && rr==rd){
        tree[p]=1;
        return 0;
    }
    else{
        int mid=(lr+rr)>>1;
        int f1, f2, f3, f4;
        if(mid>=rd)
           f1=insert(p<<1, lr, mid, ld, rd);
        else if(mid<ld)
           f2=insert(p<<1|1, mid+1, rr, ld, rd);
        else{
       f3=insert(p<<1, lr, mid, ld, mid);
       f4=insert(p<<1|1, mid+1, rr, mid+1, rd);
        }
    tree[p]=tree[p<<1] && tree[p<<1|1];//两个子树都被覆盖的时候父类才会被覆盖 
    if(mid>=rd)
       return f1;
    else if(mid<ld)
       return f2;
    else return f3 && f4;
    }
}
/*
3
1 10
1 3
6 10
如果将一个线段离散化成两个点,输出地结果是2
如果是四个节点,输出的结果就是3
而正确的结果就是3 
*/ 

int main(){
   int t, i, nm;
   scanf("%d", &t);
   while(t--){
      int maxR=0;
      scanf("%d", &n);
      for(i=0; i<n; ++i){
            scanf("%d%d", &edge[i].ld, &edge[i].rd);
            p[maxR++]=edge[i].ld-1; 
            p[maxR++]=edge[i].ld;
            p[maxR++]=edge[i].rd;
            p[maxR++]=edge[i].rd+1;
      }
      sort(p, p+maxR);
      maxR=unique(p, p+maxR)-p;//元素去重 
      for(i=0, nm=0; i<maxR; ++i){
          hash[p[i]]=++nm;
      }
      memset(tree, 0, sizeof(tree));//初始值是所有的点都没有被覆盖 
      int ans=0;
      for(i=n-1; i>=0; --i){//由外向里看真是个不错的主意 
            if(!insert(1, 1, nm, hash[edge[i].ld], hash[edge[i].rd]))
               ++ans;
      }
      printf("%d\n", ans);
   }
   return 0;
}

目录
相关文章
|
11天前
|
算法
数星星(树状数组模板题)
数星星(树状数组模板题)
|
3月前
|
机器学习/深度学习 存储 算法
回溯法求解N皇后问题
回溯法求解N皇后问题
30 0
|
4月前
cf545(线段树 + 离散化)
cf545(线段树 + 离散化)
31 0
|
Go
[Nowcoder / POJ2728] 最优比率生成树 | 二分 + prim
有n个点,其中,每个点给出位置坐标( x , y ) 以及高度z ,两点之间的距离为两点之间的欧几里得距离 两点之间建立一条路的代价为两点之间的高度差,问将n 个点联通的情况下,求出最大的cost/dis
74 0
|
人工智能 网络架构
|
Java 机器学习/深度学习
UESTC 30 &&HDU 2544最短路【Floyd求解裸题】
最短路 Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 65817    Accepted Submission(s): 28794 Problem Description 在每年的校赛里,所有进入决赛的同学都会获得一件很漂亮的t-shirt。
1097 0
|
机器学习/深度学习
回溯法——求解N皇后问题
问题描述       八皇后问题是十九世纪著名数学家高斯于1850年提出的。问题是:在8*8的棋盘上摆放8个皇后,使其不能互相攻击,即任意的两个皇后不能处在同意行,同一列,或同意斜线上。
1198 0
【OJ】贪心法 (区间问题——木棒)1129/
题目链接:点击打开链接 /* 贪心法 (区间问题——木棒)1129/ */ #include #include #include using namespace std; const int maxn=5010; typedef pair P; pairit...
938 0
推荐文章
更多