Posted on 2011-11-17 12:21
C小加 阅读(5996)
评论(0) 编辑 收藏 引用 所属分类:
解题报告
NYOJ地址：
http://acm.nyist.net/JudgeOnline/problem.php?pid=9题意：往区间[1,
10000000]的墙上贴海报，海报数量的区间是[1,10000]，后贴的会覆盖之前的，问最后能看到的海报数量。
思路：离散化+并查集。张云聪学长的方法，写着很给力啊，效率要比线段树高。离散化后从最后一张海报开始，把每一段的根节点都置为海报的起始节点，这样下一张海报访问任何一节点的时候都会直接访问到根节点，节省了访问次数。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN=30003;
inline int L(int r){return r<<1;}
inline int R(int r){return ((r<<1)+1);}
inline int MID(int l,int r) {return (l+r)>>1;}
typedef struct NODE
{
int value,zy;
bool operator < (const NODE& r) const
{
return value<r.value;
}
}NODE;
NODE node[MAXN];
int post[MAXN][2];
int f[MAXN];
bool cnt[MAXN];
int sum;
int find(int x)
{
return f[x]==-1?x:f[x]=find(f[x]);
}
int main()
{
//freopen("input","r",stdin);
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d%d",&post[i][0],&post[i][1]);//当前post为左右界坐标真值
node[L(i)].zy=-i-1;//左值为负
node[R(i)].zy=i+1;//右值为正
node[L(i)].value=post[i][0];//把左右界坐标真值储存在结构体数组中
node[R(i)].value=post[i][1];
}
sort(node,node+n*2);//对所有坐标进行排序
int count=1,temp=node[0].value;//count为离散化后坐标值。
for(int i=0;i<2*n;i++)
{
if(node[i].value!=temp)//如果坐标不同，则坐标加1
{
count++;
temp=node[i].value;
if(i!=0) //空隙处理，写的不是很好
if(node[i-1].zy>0)
if((node[i-1].value+1)!=node[i].value)
count++;
}
if(node[i].zy<0) post[-node[i].zy-1][0]=count;//新post为离散化过后，左右界值
else post[node[i].zy-1][1]=count;
}
memset(f,-1,sizeof(f));
memset(cnt,0,sizeof(cnt));
sum=0;
bool flag=0;
int l,r;
for(int i=n-1;i>=0;i--) //从最后一张海报开始
{
l=find(post[i][0]);//如果起点已经被覆盖，就找到已覆盖的最左端的节点。
for(int j=post[i][1];j>=post[i][0];j=r-1)
{
r=find(j);// 如果节点已被覆盖，找到已覆盖最左端的节点
if(!cnt[r]) //如果此节点没有被覆盖
{
cnt[r]=1;
flag=1;
}
if(l!=r) f[r]=l; //每次让右端的节点都指向最左端的节点，下次访问的时候会直接跳到最左端的节点
}
if(flag)sum++;
flag=0;
}
printf("%d\n",sum);
}
return 0;
}