Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:实在没办法了,贴一下自己WA的代码(有详细的注释),哪位大牛帮我看一下,或者给几组我过不了的数据,小弟不胜感激!!In Reply To:实在没办法了,贴一下自己WA的代码(有详细的注释),哪位大牛帮我看一下,或者给几组我过不了的数据,小弟不胜感激!! Posted by:new_begin at 2009-09-20 02:09:49 > #include<iostream> > #include<algorithm> > > using namespace std; > > const int N=50005; > > struct point > { > int x,y; > bool operator<(const point&bb)const > { > if(x!=bb.x) > return x>bb.x; > return y>bb.x; > } > } p[N]; > struct node > { > int y,num; > bool operator<(const node&bb)const > { > return y<bb.y; > } > } q[N]; > int a[N],yy[N]; > int n; > > int lowbit(int x) > { > return x&(-x); > } > int getsum(int x) > { > int i,sum; > if(x==0) > return 0; > sum=0; > i=x; > while(i>0) > { > sum+=a[i]; > i-=lowbit(i); > } > return sum; > } > void change(int x) > { > int i=x; > while(i<=n) > { > a[i]++; > i+=lowbit(i); > } > return; > } > > int main() > { > int i,j,sum,u,v; > while(scanf("%d",&n)==1&&n) > { > i=1; > while(i<=n) > { > scanf("%d%d",&p[i].x,&p[i].y); > i++; > } > sort(p+1,p+n+1);//对x坐标排序,如果x坐标相等,按y坐标排序。 > > //离散化,离散化后的y坐标值保存在yy数组中。 > i=1; > while(i<=n) > { > q[i].y=p[i].y; > q[i].num=i; > i++; > } > sort(q+1,q+n+1); > j=1; > yy[q[1].num]=1; > i=2; > while(i<=n) > { > if(q[i].y!=q[i-1].y) > { > ++j; > yy[q[i].num]=j; > } > else yy[q[i].num]=j; > i++; > } > //树状数组。 > memset(a,0,sizeof(a)); > change(yy[1]);//每插入一个y值,就在树状数组相应点加1。 > sum=1; > i=2; > while(i<=n) > { > change(yy[i]); > u=getsum(yy[i]); > v=getsum(yy[i]-1); > //当前y值比之前插入的y值都要大,则sum加1,即1到yy[i]得和为i,而yy[i]这点为1。 > if(u==i&&v==i-1) > sum++; > i++; > } > printf("%d\n",sum); > } > return 0; > } > > > > Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator