| ||||||||||
| 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