鱼C论坛

 找回密码
 立即注册
查看: 154|回复: 7

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

[复制链接]
发表于 7 天前 | 显示全部楼层 |阅读模式
3鱼币
屏幕截图 2021-11-18 165009.png
最佳答案
7 天前
本帖最后由 jhq999 于 2021-11-26 07:08 编辑
  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.         printf("%d %d %d",hrs[0].id,hrs[1].id,hrs[2].id);
  41.         delete[] hrs;
  42.         return 0;
  43. }
复制代码
  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
复制代码

最佳答案

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 7 天前 | 显示全部楼层    本楼为最佳答案   
本帖最后由 jhq999 于 2021-11-26 07:08 编辑
  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.         printf("%d %d %d",hrs[0].id,hrs[1].id,hrs[2].id);
  41.         delete[] hrs;
  42.         return 0;
  43. }
复制代码
  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
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 6 天前 From FishC Mobile | 显示全部楼层
jhq999 发表于 2021-11-26 06:52

题目内容写明:N <= 10000,你的代码中 for 嵌套另一个 for,时间复杂度提升至 O(N^2) 不超时吗?
这题做法简单,难在超时部分
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 6 天前 From FishC Mobile | 显示全部楼层
本帖最后由 傻眼貓咪 于 2021-11-26 11:18 编辑
  1. #include <stdio.h>

  2. int main() {
  3.     int N, first, second, third;
  4.     float x = 32767, y = 32767, z = 32767;
  5.     scanf("%d", &N);
  6.     for(size_t i = 0; i < N; i++){
  7.         int a;
  8.         float b, c;
  9.         scanf("%d%f%f", &a, &b, &c);
  10.         if(b/c <= x){
  11.             z = y;
  12.             y = x;
  13.             x = b/c;
  14.             
  15.             third = second;
  16.             second = first;
  17.             first = a;
  18.         }
  19.         else if(b/c <= y){
  20.             z = y;
  21.             y = b/c;
  22.             
  23.             third = second;
  24.             second = a;
  25.         }
  26.         else if(b/c <= z){
  27.             z = b/c;
  28.             third = a;
  29.         }
  30.     }
  31.     int max, min, mid;
  32.     max = first > second ? first : second > third ? second : third;
  33.     min = first < second ? first : second < third ? second : third;
  34.     mid = first != max && first != min ? first : second != max && second != min ? second : third;
  35.     (x != y) && (x != z) && (y != z) ? printf("%d %d %d", first, second, third) :\
  36.     (x == y) && (x != z) ? printf("%d %d %d", first < second ? first : second, first > second ? first : second, third) :\
  37.     (y == z) && (y != x) ? printf("%d %d %d", first, second < third ? second : third, second > third ? first : second) :\
  38.     printf("%d %d %d", min, mid, max);
  39.     return 0;
  40. }
复制代码
**我刚刚用手机写代码,没有检查是否正确
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 6 天前 | 显示全部楼层

N

本帖最后由 jhq999 于 2021-11-26 13:07 编辑
傻眼貓咪 发表于 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.         while (i<num)
  21.         {
  22.                 sprintf(ch,"%d %d %d",i,rand()%1000+1,rand()%20+1);
  23.                 sscanf(ch,"%d %d %d",&hrs[i].id,&hrs[i].distance,&hrs[i].speed);
  24.                 hrs[i].time=(float)hrs[i].distance/hrs[i].speed;
  25.                 i++;
  26.         }
  27.     time_t start,end;
  28.         time(&start);
  29.         for ( i = 0; i < 3; i++)
  30.         {
  31.                 for (j = i+1; j < num; j++)
  32.                 {
  33.                         if(hrs[i].time>hrs[j].time)
  34.                         {
  35.                                 tmp=hrs[i];
  36.                                 hrs[i]=hrs[j];
  37.                                 hrs[j]=tmp;
  38.                         }

  39.                 }
  40.         }
  41.         Sleep(1000);//暂停一秒
  42.         time(&end);
  43.         double cost=difftime(end,start);
  44.         printf("%lf\n%d %d %d",cost,hrs[0].id,hrs[1].id,hrs[2].id);
  45.         delete[] hrs;
  46.         return 0;
  47. }
复制代码

  1. 10000
  2. 1.000000
  3. 4912 6429 235
复制代码

评分

参与人数 1荣誉 +1 鱼币 +1 收起 理由
傻眼貓咪 + 1 + 1 鱼C有你更精彩^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 6 天前 From FishC Mobile | 显示全部楼层
jhq999 发表于 2021-11-26 12:16
没看着题目有限制时间?没考虑到时间复杂度。但两个for的时间复杂度是O(3×N-3)不是O(N^2),就算直接排 ...

受教了,謝謝
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
 楼主| 发表于 3 天前 | 显示全部楼层
傻眼貓咪 发表于 2021-11-26 09:54
**我刚刚用手机写代码,没有检查是否正确

输出格式还有个要求,如有并列,按编号递增去前面的输出
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 3 天前 | 显示全部楼层
注册名字可真难 发表于 2021-11-29 14:56
输出格式还有个要求,如有并列,按编号递增去前面的输出

好的,没有注意到,粗心了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1

GMT+8, 2021-12-2 00:33

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表