Posted on 2011-11-17 12:21
C小加 閱讀(6006)
評論(0) 編輯 收藏 引用 所屬分類:
解題報(bào)告
NYOJ地址：
http://acm.nyist.net/JudgeOnline/problem.php?pid=9題意：往區(qū)間[1,
10000000]的墻上貼海報(bào)，海報(bào)數(shù)量的區(qū)間是[1,10000]，后貼的會(huì)覆蓋之前的，問最后能看到的海報(bào)數(shù)量。
思路：離散化+并查集。張?jiān)坡攲W(xué)長的方法，寫著很給力啊，效率要比線段樹高。離散化后從最后一張海報(bào)開始，把每一段的根節(jié)點(diǎn)都置為海報(bào)的起始節(jié)點(diǎn)，這樣下一張海報(bào)訪問任何一節(jié)點(diǎn)的時(shí)候都會(huì)直接訪問到根節(jié)點(diǎn)，節(jié)省了訪問次數(shù)。
#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]);//當(dāng)前post為左右界坐標(biāo)真值
node[L(i)].zy=-i-1;//左值為負(fù)
node[R(i)].zy=i+1;//右值為正
node[L(i)].value=post[i][0];//把左右界坐標(biāo)真值儲存在結(jié)構(gòu)體數(shù)組中
node[R(i)].value=post[i][1];
}
sort(node,node+n*2);//對所有坐標(biāo)進(jìn)行排序
int count=1,temp=node[0].value;//count為離散化后坐標(biāo)值。
for(int i=0;i<2*n;i++)
{
if(node[i].value!=temp)//如果坐標(biāo)不同，則坐標(biāo)加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--) //從最后一張海報(bào)開始
{
l=find(post[i][0]);//如果起點(diǎn)已經(jīng)被覆蓋，就找到已覆蓋的最左端的節(jié)點(diǎn)。
for(int j=post[i][1];j>=post[i][0];j=r-1)
{
r=find(j);// 如果節(jié)點(diǎn)已被覆蓋，找到已覆蓋最左端的節(jié)點(diǎn)
if(!cnt[r]) //如果此節(jié)點(diǎn)沒有被覆蓋
{
cnt[r]=1;
flag=1;
}
if(l!=r) f[r]=l; //每次讓右端的節(jié)點(diǎn)都指向最左端的節(jié)點(diǎn)，下次訪問的時(shí)候會(huì)直接跳到最左端的節(jié)點(diǎn)
}
if(flag)sum++;
flag=0;
}
printf("%d\n",sum);
}
return 0;
}