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

注册名字可真难

最佳答案

月排行榜 / 总排行榜

jhq999

2021-11-25 19:21:58

1. typedef struct HORSE
   
2. {
   
3.         int id;
   
4.         int distance;
   
5.         int speed;
   
6.         float time;
   
7. }Horse,*pHorse;
   
8. int main()
   
9. {
   
10.         int num=0,i=0,j=0;
    
11.         Horse tmp={0};
    
12.         scanf("%d",&num);
    
13.         pHorse hrs=new HORSE[num];
    
14.         i=0;
    
15.         while (i<num)
    
16.         {
    
17.                 scanf("%d %d %d",&hrs[i].id,&hrs[i].distance,&hrs[i].speed);
    
18.                 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)
    
19.                {
    
20.                    if(hrs[i].id<1||hrs[i].id>10000)printf("序号错误。");
    
21.                    if(hrs[i].distance<1||hrs[i].distance>1000)printf("距离错误。");
    
22.                    if(hrs[i].speed<0||hrs[i].speed>20)printf("速度错误。");
    
23.                    continue;
    
24.                 }
    
25.                 hrs[i].time=(float)hrs[i].distance/hrs[i].speed;
    
26.                 i++;
    
27.         }
    
28.         for ( i = 0; i < 3; i++)
    
29.         {
    
30.                 for (j = i+1; j < num; j++)
    
31.                 {
    
32.                         if(hrs[i].time>hrs[j].time)
    
33.                         {
    
34.                                 tmp=hrs[i];
    
35.                                 hrs[i]=hrs[j];
    
36.                                 hrs[j]=tmp;
    
37.                         }
    
38. 
    
39.                 }
    
40.         }
    
41.         printf("%d %d %d",hrs[0].id,hrs[1].id,hrs[2].id);
    
42.         delete[] hrs;
    
43.         return 0;
    
44. }

复制代码

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

复制代码

跳转到最佳答案楼层

jhq999

1. typedef struct HORSE
   
2. {
   
3.         int id;
   
4.         int distance;
   
5.         int speed;
   
6.         float time;
   
7. }Horse,*pHorse;
   
8. int main()
   
9. {
   
10.         int num=0,i=0,j=0;
    
11.         Horse tmp={0};
    
12.         scanf("%d",&num);
    
13.         pHorse hrs=new HORSE[num];
    
14.         i=0;
    
15.         while (i<num)
    
16.         {
    
17.                 scanf("%d %d %d",&hrs[i].id,&hrs[i].distance,&hrs[i].speed);
    
18.                 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)
    
19.                {
    
20.                    if(hrs[i].id<1||hrs[i].id>10000)printf("序号错误。");
    
21.                    if(hrs[i].distance<1||hrs[i].distance>1000)printf("距离错误。");
    
22.                    if(hrs[i].speed<0||hrs[i].speed>20)printf("速度错误。");
    
23.                    continue;
    
24.                 }
    
25.                 hrs[i].time=(float)hrs[i].distance/hrs[i].speed;
    
26.                 i++;
    
27.         }
    
28.         for ( i = 0; i < 3; i++)
    
29.         {
    
30.                 for (j = i+1; j < num; j++)
    
31.                 {
    
32.                         if(hrs[i].time>hrs[j].time)
    
33.                         {
    
34.                                 tmp=hrs[i];
    
35.                                 hrs[i]=hrs[j];
    
36.                                 hrs[j]=tmp;
    
37.                         }
    
38. 
    
39.                 }
    
40.         }
    
41.         printf("%d %d %d",hrs[0].id,hrs[1].id,hrs[2].id);
    
42.         delete[] hrs;
    
43.         return 0;
    
44. }

复制代码

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

复制代码

傻眼貓咪

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

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

傻眼貓咪

1. #include <stdio.h>
   
2. 
   
3. int main() {
   
4.     int N, first, second, third;
   
5.     float x = 32767, y = 32767, z = 32767;
   
6.     scanf("%d", &N);
   
7.     for(size_t i = 0; i < N; i++){
   
8.         int a;
   
9.         float b, c;
   
10.         scanf("%d%f%f", &a, &b, &c);
    
11.         if(b/c <= x){
    
12.             z = y;
    
13.             y = x;
    
14.             x = b/c;
    
15.             
    
16.             third = second;
    
17.             second = first;
    
18.             first = a;
    
19.         }
    
20.         else if(b/c <= y){
    
21.             z = y;
    
22.             y = b/c;
    
23.             
    
24.             third = second;
    
25.             second = a;
    
26.         }
    
27.         else if(b/c <= z){
    
28.             z = b/c;
    
29.             third = a;
    
30.         }
    
31.     }
    
32.     int max, min, mid;
    
33.     max = first > second ? first : second > third ? second : third;
    
34.     min = first < second ? first : second < third ? second : third;
    
35.     mid = first != max && first != min ? first : second != max && second != min ? second : third;
    
36.     (x != y) && (x != z) && (y != z) ? printf("%d %d %d", first, second, third) :\
    
37.     (x == y) && (x != z) ? printf("%d %d %d", first < second ? first : second, first > second ? first : second, third) :\
    
38.     (y == z) && (y != x) ? printf("%d %d %d", first, second < third ? second : third, second > third ? first : second) :\
    
39.     printf("%d %d %d", min, mid, max);
    
40.     return 0;
    
41. }

复制代码

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

jhq999

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

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

1. #include <stdlib.h>
   
2. #include <time.h>
   
3. #include <Windows.h>
   
4. typedef struct HORSE
   
5. {
   
6.         int id;
   
7.         int distance;
   
8.         int speed;
   
9.         float time;
   
10. }Horse,*pHorse;
    
11. int main()
    
12. {
    
13.         char ch[256]={0};
    
14.         int num=0,i=0,j=0;
    
15.         Horse tmp={0};
    
16.         scanf("%d",&num);
    
17.         pHorse hrs=new HORSE[num];
    
18.         i=0;
    
19.         srand((unsigned int)time(0));
    
20. 
    
21.         while (i<num)
    
22.         {
    
23.                 sprintf(ch,"%d %d %d",i,rand()%1000+1,rand()%20+1);
    
24.                 sscanf(ch,"%d %d %d",&hrs[i].id,&hrs[i].distance,&hrs[i].speed);
    
25.                 hrs[i].time=(float)hrs[i].distance/hrs[i].speed;
    
26.                 i++;
    
27.         }
    
28.     time_t start,end;
    
29.         time(&start);
    
30.         for ( i = 0; i < 3; i++)
    
31.         {
    
32.                 for (j = i+1; j < num; j++)
    
33.                 {
    
34.                         if(hrs[i].time>hrs[j].time)
    
35.                         {
    
36.                                 tmp=hrs[i];
    
37.                                 hrs[i]=hrs[j];
    
38.                                 hrs[j]=tmp;
    
39.                         }
    
40. 
    
41.                 }
    
42.         }
    
43.         Sleep(1000);//暂停一秒
    
44.         time(&end);
    
45.         double cost=difftime(end,start);
    
46.         printf("%lf\n%d %d %d",cost,hrs[0].id,hrs[1].id,hrs[2].id);
    
47.         delete[] hrs;
    
48.         return 0;
    
49. }

复制代码

1. 10000
   
2. 1.000000
   
3. 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
输出格式还有个要求，如有并列，按编号递增去前面的输出

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