Posted on 2011-11-17 12:21
C小加 閱讀(6024)
評論(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;
}