注册名字可真难 发表于 2021-11-25 19:21:57

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

jhq999 发表于 2021-11-25 19:21:58

本帖最后由 jhq999 于 2021-11-26 07:08 编辑

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;
        i=0;
        while (i<num)
        {
                scanf("%d %d %d",&hrs.id,&hrs.distance,&hrs.speed);
                if(hrs.id<1||hrs.id>10000||hrs.distance<1||hrs.distance>1000||hrs.speed<0||hrs.speed>20)
               {
                   if(hrs.id<1||hrs.id>10000)printf("序号错误。");
                   if(hrs.distance<1||hrs.distance>1000)printf("距离错误。");
                   if(hrs.speed<0||hrs.speed>20)printf("速度错误。");
                   continue;
                }
                hrs.time=(float)hrs.distance/hrs.speed;
                i++;
        }
        for ( i = 0; i < 3; i++)
        {
                for (j = i+1; j < num; j++)
                {
                        if(hrs.time>hrs.time)
                        {
                                tmp=hrs;
                                hrs=hrs;
                                hrs=tmp;
                        }

                }
        }
        printf("%d %d %d",hrs.id,hrs.id,hrs.id);
        delete[] hrs;
        return 0;
}
   5
1 20 12
2 21 11
3 25 13
4 10 10
5 7 8
5 4 1

傻眼貓咪 发表于 2021-11-26 09:33:57

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


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

傻眼貓咪 发表于 2021-11-26 09:54:18

本帖最后由 傻眼貓咪 于 2021-11-26 11:18 编辑

#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 12:16:01

N

本帖最后由 jhq999 于 2021-11-26 13:07 编辑

傻眼貓咪 发表于 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={0};
        int num=0,i=0,j=0;
        Horse tmp={0};
        scanf("%d",&num);
        pHorse hrs=new HORSE;
        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.id,&hrs.distance,&hrs.speed);
                hrs.time=(float)hrs.distance/hrs.speed;
                i++;
        }
    time_t start,end;
        time(&start);
        for ( i = 0; i < 3; i++)
        {
                for (j = i+1; j < num; j++)
                {
                        if(hrs.time>hrs.time)
                        {
                                tmp=hrs;
                                hrs=hrs;
                                hrs=tmp;
                        }

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

傻眼貓咪 发表于 2021-11-26 14:05:52

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

受教了，謝謝

注册名字可真难 发表于 2021-11-29 14:56:27

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

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

傻眼貓咪 发表于 2021-11-29 17:31:51

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

好的，没有注意到，粗心了{:5_108:}
页: [1]
查看完整版本: PTA赌马 求C语言实现 有文字解释就更好了