标题:还是杭电1052田忌赛马
只看楼主
conquerorbzm
Rank: 2
等 级:论坛游民
帖 子:35
专家分:33
注 册:2010-7-23
结帖率:77.78%
已结贴  问题点数:20 回复次数:2 
还是杭电1052田忌赛马
//昨天那个算法漏洞挺大,但我重新构思了,但运行到312ms还是wa了。我测试了许多数据,结果是对的,郁闷了,谁能救救我啊?
#include"stdio.h"                                    
void sort(int s[],int n,int d[])                    //选择排序
{
    int i,j,t,k,e;
    for(i=0;i<n-1;i++)
    {
        k=i;
        for(j=i+1;j<n;j++)
            if(s[k]<s[j])
                k=j;
        if(k!=i)
        {
            t=s[i];
            s[i]=s[k];
            s[k]=t;
            e=d[i];
            d[i]=d[k];
            d[k]=e;
        }
    }
}
int main()
{
    void sort(int s[],int n,int d[]);
    int i,j,k,n,e,m;                                
    int a[1001]={0},b[1001]={0},c[1001]={3};        //a用来存田忌马的数据,b存齐王的,c用来记录胜负平。
    long sum;
    while(scanf("%d",&n)!=EOF&&n!=0)
    {   
        for(i=0;i<n;i++)                            //首先我把c中元素都赋为3.
            c[i]=3;
        k=0;sum=0;e=0;                                    
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        for(i=0;i<n;i++)
            scanf("%d",&b[i]);                        
        sort(a,n,c);                                //第一次进行排序。
        sort(b,n,c);                                
        for(i=0;i<n;i++)                            //在同一级别的能赢的就一定赢下来。
        {
            if(a[i]>b[i])                            //赢了后c[i]=1,a[i]=-1,b[i]=-1,e用来记录同一级别赢得马的个数。
            {
                c[i]=1;
                a[i]=-1;
                b[i]=-1;
                e++;
            }
        }
        sort(a,n,c);                                //第二次排序,把那些赢得马排到后面去。
        sort(b,n,c);
        for(i=0;i<n-e;i++)                            //剩下的马,田忌的马都是小于或等于齐王的马。所以田忌的马能赢齐王的马就尽量赢。
        {                                            //不能赢得我就尽量平。
            m=0;
            for(j=0;j<n-e;j++)
            {   
                if(b[j]==-1)
                    continue;
                if(a[i]>b[j])
                {
                    c[i]=1;
                    b[j]=-1;
                    m=1;                            //这里m是,我赢了齐王得马,就不必去平他的马。
                    break;
                }
            }
            for(j=0;j<n-e;j++)                        
            {   
                if(m)
                    break;
                if(b[j]==-1)
                    continue;
                if(a[i]==b[j])
                {
                    c[i]=0;
                    b[j]=-1;
                    break;
                }
            }
        }
        for(i=0;i<n;i++)                            //剩下的马都输了,我记为-1.               
            if(c[i]>1)
                c[i]=-1;
        for(i=0;i<n;i++)                            //求赢得的总钱。
        {
            if(c[i]==1)
                sum+=200;
            if(c[i]==-1)
                sum-=200;
        }
        printf("%ld\n",sum);
    }
    return 0;
}
//我测试了许多数据,都是对的,但肯定有组过不了,应该哪里还有漏洞,欢迎各位大侠帮忙纠错,或者发表你的看法,什么意见都欢迎。你也可以把好算法沾上去,互相讨论,主要帮我看看哪错了,我将不胜感激。
        
搜索更多相关主题的帖子: 赛马 田忌 
2010-08-07 10:55
playmyself
Rank: 5Rank: 5
来 自:第3系4级宇宙空间
等 级:职业侠客
帖 子:76
专家分:399
注 册:2009-7-8
得分:20 
你代码太长了,没时间看,我有事得立即走了,给你组让你WA的数据,你自己调试吧。
3
6 4 1
2 1 1
应该是400,你输出0,估计小毛病,可能改个什么就好了。
另附我写的:
程序代码:
#include <stdio.h>
#include <stdlib.h>
int kh[1000], th[1000];

int cmp(const void *a, const void *b)
{
    return (*(int *)b-*(int *)a);
}
int main(void)
{
    int N, i, j, k, mxt, mxk, w;
    while(scanf("%d", &N),N)
    {
        for(i = 0; i < N; ++i)
            scanf("%d", &th[i]);
        qsort(th, i, sizeof(th[0]), cmp);
        for(i = 0; i < N; ++i)
            scanf("%d", &kh[i]);
        qsort(kh, i, sizeof(kh[0]), cmp);
       
        w = k = j = 0;
        mxk = mxt = N-1;
        for(i = 0; i < N; ++i)
        {
            if(th[j] > kh[k])
                ++w, ++j, ++k;
            else if(th[mxt] > kh[mxk])
                ++w, --mxt, --mxk;
            else if(th[mxt] < kh[k])
                --w, --mxt, ++k;
            else;
        }
        printf("%d\n", 200*w);
    }
    return 0;
}


无聊创造奇迹。
2010-08-07 16:00
conquerorbzm
Rank: 2
等 级:论坛游民
帖 子:35
专家分:33
注 册:2010-7-23
得分:0 
回复 2楼 playmyself
谢谢了
2010-08-07 19:46



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-315028-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.064523 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved