[已解决]PTA赌马 求C语言实现 有文字解释就更好了

注册名字可真难

最佳答案

月排行榜 / 总排行榜

jhq999

2021-11-25 19:21:58

typedef struct HORSE
{
        int id;
        int distance;
        int speed;
        float time;
}Horse,*pHorse;
int main()
{
        int num=0,i=0,j=0;
        Horse tmp={0};
        scanf("%d",&num);
        pHorse hrs=new HORSE[num];
        i=0;
        while (i<num)
        {
                scanf("%d %d %d",&hrs[i].id,&hrs[i].distance,&hrs[i].speed);
                if(hrs[i].id<1||hrs[i].id>10000||hrs[i].distance<1||hrs[i].distance>1000||hrs[i].speed<0||hrs[i].speed>20)
               {
                   if(hrs[i].id<1||hrs[i].id>10000)printf("序号错误。");
                   if(hrs[i].distance<1||hrs[i].distance>1000)printf("距离错误。");
                   if(hrs[i].speed<0||hrs[i].speed>20)printf("速度错误。");
                   continue;
                }
                hrs[i].time=(float)hrs[i].distance/hrs[i].speed;
                i++;
        }
        for ( i = 0; i < 3; i++)
        {
                for (j = i+1; j < num; j++)
                {
                        if(hrs[i].time>hrs[j].time)
                        {
                                tmp=hrs[i];
                                hrs[i]=hrs[j];
                                hrs[j]=tmp;
                        }

                }
        }
        printf("%d %d %d",hrs[0].id,hrs[1].id,hrs[2].id);
        delete[] hrs;
        return 0;
}

   5
1 20 12
2 21 11
3 25 13
4 10 10
5 7 8
5 4 1

跳转到最佳答案楼层

jhq999

typedef struct HORSE
{
        int id;
        int distance;
        int speed;
        float time;
}Horse,*pHorse;
int main()
{
        int num=0,i=0,j=0;
        Horse tmp={0};
        scanf("%d",&num);
        pHorse hrs=new HORSE[num];
        i=0;
        while (i<num)
        {
                scanf("%d %d %d",&hrs[i].id,&hrs[i].distance,&hrs[i].speed);
                if(hrs[i].id<1||hrs[i].id>10000||hrs[i].distance<1||hrs[i].distance>1000||hrs[i].speed<0||hrs[i].speed>20)
               {
                   if(hrs[i].id<1||hrs[i].id>10000)printf("序号错误。");
                   if(hrs[i].distance<1||hrs[i].distance>1000)printf("距离错误。");
                   if(hrs[i].speed<0||hrs[i].speed>20)printf("速度错误。");
                   continue;
                }
                hrs[i].time=(float)hrs[i].distance/hrs[i].speed;
                i++;
        }
        for ( i = 0; i < 3; i++)
        {
                for (j = i+1; j < num; j++)
                {
                        if(hrs[i].time>hrs[j].time)
                        {
                                tmp=hrs[i];
                                hrs[i]=hrs[j];
                                hrs[j]=tmp;
                        }

                }
        }
        printf("%d %d %d",hrs[0].id,hrs[1].id,hrs[2].id);
        delete[] hrs;
        return 0;
}

   5
1 20 12
2 21 11
3 25 13
4 10 10
5 7 8
5 4 1

傻眼貓咪

jhq999 发表于 2021-11-26 06:52

题目内容写明：N <= 10000，你的代码中 for 嵌套另一个 for，时间复杂度提升至 O(N^2) 不超时吗？
这题做法简单，难在超时部分

傻眼貓咪

#include <stdio.h>

int main() {
    int N, first, second, third;
    float x = 32767, y = 32767, z = 32767;
    scanf("%d", &N);
    for(size_t i = 0; i < N; i++){
        int a;
        float b, c;
        scanf("%d%f%f", &a, &b, &c);
        if(b/c <= x){
            z = y;
            y = x;
            x = b/c;
            
            third = second;
            second = first;
            first = a;
        }
        else if(b/c <= y){
            z = y;
            y = b/c;
            
            third = second;
            second = a;
        }
        else if(b/c <= z){
            z = b/c;
            third = a;
        }
    }
    int max, min, mid;
    max = first > second ? first : second > third ? second : third;
    min = first < second ? first : second < third ? second : third;
    mid = first != max && first != min ? first : second != max && second != min ? second : third;
    (x != y) && (x != z) && (y != z) ? printf("%d %d %d", first, second, third) :\
    (x == y) && (x != z) ? printf("%d %d %d", first < second ? first : second, first > second ? first : second, third) :\
    (y == z) && (y != x) ? printf("%d %d %d", first, second < third ? second : third, second > third ? first : second) :\
    printf("%d %d %d", min, mid, max);
    return 0;
}

**我刚刚用手机写代码，没有检查是否正确

jhq999

傻眼貓咪 发表于 2021-11-26 09:54
**我刚刚用手机写代码，没有检查是否正确

没看着题目有限制时间？没考虑到时间复杂度。但两个for的时间复杂度是O(3×N-3)不是O(N^2)，就算直接排序也不会是O(N^2)

#include <stdlib.h>
#include <time.h>
#include <Windows.h>
typedef struct HORSE
{
        int id;
        int distance;
        int speed;
        float time;
}Horse,*pHorse;
int main()
{
        char ch[256]={0};
        int num=0,i=0,j=0;
        Horse tmp={0};
        scanf("%d",&num);
        pHorse hrs=new HORSE[num];
        i=0;
        srand((unsigned int)time(0));

        while (i<num)
        {
                sprintf(ch,"%d %d %d",i,rand()%1000+1,rand()%20+1);
                sscanf(ch,"%d %d %d",&hrs[i].id,&hrs[i].distance,&hrs[i].speed);
                hrs[i].time=(float)hrs[i].distance/hrs[i].speed;
                i++;
        }
    time_t start,end;
        time(&start);
        for ( i = 0; i < 3; i++)
        {
                for (j = i+1; j < num; j++)
                {
                        if(hrs[i].time>hrs[j].time)
                        {
                                tmp=hrs[i];
                                hrs[i]=hrs[j];
                                hrs[j]=tmp;
                        }

                }
        }
        Sleep(1000);//暂停一秒
        time(&end);
        double cost=difftime(end,start);
        printf("%lf\n%d %d %d",cost,hrs[0].id,hrs[1].id,hrs[2].id);
        delete[] hrs;
        return 0;
}

10000
1.000000
4912 6429 235

傻眼貓咪

jhq999 发表于 2021-11-26 12:16
没看着题目有限制时间？没考虑到时间复杂度。但两个for的时间复杂度是O(3×N-3)不是O(N^2)，就算直接排 ...

受教了，謝謝

注册名字可真难

傻眼貓咪 发表于 2021-11-26 09:54
**我刚刚用手机写代码，没有检查是否正确

输出格式还有个要求，如有并列，按编号递增去前面的输出

傻眼貓咪

注册名字可真难 发表于 2021-11-29 14:56
输出格式还有个要求，如有并列，按编号递增去前面的输出

好的，没有注意到，粗心了