问题描述

来大神帮看看 ACM_51nod_1289

网站

#include <stdio.h>

struct fish
{
    int dx,fx,vis;
} a[100005];

int main()
{
    int n,i,j,ans,lmax,rmax,l,r;
    scanf("%d",&n);
    ans=n;
    lmax=rmax=0;
    l=1;
    r=n;
    for(i=1; i<=n; i++)
    {
        scanf("%d %d",&a[i].dx,&a[i].fx);
        if(a[i].fx==1&&lmax==0)
        {
            lmax=a[i].dx;
            l=i;
        }//找向右游的第一个
        if(a[i].fx==0)
        {
            rmax=a[i].dx;
            r=i;
        }//从右边起找 向左游的第一个
        a[i].vis=1;
    }
//    printf("%d %d %d %dn",l,lmax,r,rmax);
    for(i=l+1,j=r-1; i<=n&&j>=1; i++,j--)
    {
        if(a[i].vis)//将要面对的鱼活着
        {
            if(a[i].fx==0)//向左游的
            {
                if(a[l].vis)//大鱼活着
                {
                    if(lmax>a[i].dx)//能吃
                    {
                        ans--;
                        a[i].vis=0;//吃掉
                    }
                    else
                    {
                        ans--;
                        a[l].vis=0;//被吃掉
                    }
                }
            }
            else //同方向的
            {
                if(lmax<a[i].dx||a[l].vis==0) //比我大 或者大鱼被吃 补充
                {
                    lmax=a[i].dx;//你做老大
                    l=i;
                }
            }
        }

        if(a[j].vis)
        {
            if(a[j].fx==1)
            {
                if(a[r].vis)
                {
                    if(rmax>a[j].dx)
                    {
                        ans--;
                        a[j].vis=0;
                    }
                    else
                    {
                        ans--;
                        a[r].vis=0;
                    }
                }
            }
            else
            {
                if(rmax<a[j].dx||a[r].vis==0)
                {
                    rmax=a[j].dx;
                    r=j;
                }
            }
        }
    }

    for(i--; i<=n; i++)
    {
        if(a[i].vis)
        {
            if(a[i].fx==0)
            {
                if(a[l].vis)
                {
                    if(lmax>a[i].dx)//能吃
                    {
                        ans--;
                        a[i].vis=0;//吃掉
                    }
                    else
                    {
                        ans--;
                        a[l].vis=0;//被吃掉
                    }
                }
            }
            else
            {
                if(lmax<a[i].dx||a[l].vis==0)
                {
                    lmax=a[i].dx;
                    l=i;
                }
            }
        }
    }

    for(j++; j>=1; j--)
    {
        if(a[j].vis)
        {
            if(a[j].fx==1)
            {
                if(a[r].vis)
                {
                    if(rmax>a[j].dx)
                    {
                        ans--;
                        a[j].vis=0;
                    }
                    else
                    {
                        ans--;
                        a[r].vis=0;
                    }
                }
            }
            else
            {
                if(rmax<a[j].dx||a[r].vis==0)
                {
                    rmax=a[j].dx;
                    r=j;
                }
            }
        }
    }
    printf("%dn",ans);
    return 0;
}

过了三个样例 实在找不到哪里有问题 有大神帮我看看吗

解决方案

这问题也太模糊了。。。。
struct fish
{
int dx,fx,vis;
} a[100005]
这里的结构体数组最好可以动态非配，静态分配可能会出现运行内存过大的问题