MyException - 我的异常网
当前位置:我的异常网» 编程 » 10131 - Is Bigger Smarter

10131 - Is Bigger Smarter

www.myexceptions.net  网友分享于:2013-04-10  浏览:4次
10131 - Is Bigger Smarter?
描述:题意很简单,先快排一下,然后从中选择即可,因为我觉得只用数组有些麻烦,所以用了结构体
#include <cstdio>
#include <cstdlib>
struct Ele
{
    int We;
    int Iq;
    int sum;
    int next;
    int pos;
};
Ele count[1010];
int cmp(const void *p1 ,const void *p2)
{
    int p1_We=((Ele *)p1)->We,p1_Iq=((Ele *)p1)->Iq;
    int p2_We=((Ele *)p2)->We,p2_Iq=((Ele *)p2)->Iq;
    if(p1_We>p2_We) return 1;
    else if(p1_We<p2_We) return -1;
    else
    {
        if(p1_Iq>p2_Iq) return -1;
        else return 1;
    }
}
int main()
{
    //freopen("a.txt","r",stdin);
    int x,y,len=0;
    while(scanf("%d %d",&x,&y)!=EOF)
    {
        count[len].We=x;
        count[len].Iq=y;
        count[len].sum=1;
        count[len].next=-1;
        count[len].pos=len+1;
        len++;
    }
    qsort(count,len,sizeof(Ele),cmp);
    for(int i=len-2; i>=0; i--)
    {
        y=x=-1;
        for(int j=len-1; j>i; j--)
            if(count[i].We<count[j].We&&count[i].Iq>count[j].Iq)
            {
                if(x==-1)
                {
                    x=count[j].sum;
                    y=j;
                }
                else if(x<count[j].sum)
                {
                    x=count[j].sum;
                    y=j;
                }
            }
        count[i].sum+=count[y].sum;
        count[i].next=y;
    }
    y=0;
    x=count[0].sum;
    for(int i=1; i<len; i++)
        if(x<count[i].sum)
        {
            x=count[i].sum;
            y=i;
        }
    printf("%d\n",x);
    while(y!=-1)
    {
        printf("%d\n",count[y].pos);
        y=count[y].next;
    }
    return 0;
}

文章评论

软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有