田忌赛马

萨西摩尔·槿花

田忌赛马
输入
输入最多包含 50 个测试用例。每种情况都以第一行的正整数 n （n <= 1000） 开头，这是每边的马数。第二行接下来的n个整数是田氏马的速度。然后第三行的下一个n个整数是国王马的速度。输入以一行结尾，该行在最后一个测试用例之后具有单个 0。
输出
对于每个输入案例，输出一行包含单个数字，每赢一场得200银元。这是田机将获得的最大金额，以银元为单位。

示例输入
3
92 83 71
95 87 74
2
20 20
20 20
2
20 19
22 18
0

示例输出
200
0
0

1. #include "stdio.h"
   
2. #include <stdlib.h>
   
3. int compare(const void *b, const void *a)
   
4. {
   
5.     return *(int*)a - *(int*)b;
   
6. }
   
7. 
   
8. int main()
   
9. {
   
10.         int c,i,win,ave,j,temp,tj[1001]={0},gw[1001]={0},k;
    
11.         while(scanf("%d",&c)&&c!=0)
    
12.         {
    
13.                 for(i=0;i<c;i++)
    
14.                 {
    
15.                         scanf("%d",&tj[i]);
    
16.                 }
    
17.                 for(i=0;i<c;i++)
    
18.                 {
    
19.                         scanf("%d",&gw[i]);
    
20.                 }
    
21.                 qsort(tj, c, sizeof(int), compare);//田忌的马降序
    
22.                 qsort(gw, c, sizeof(int), compare);//国王的马降序
    
23.                 win=0;//胜场数
    
24.                 ave=0;//平局数
    
25.                 temp=-1; //king的马从temp开始， 之前的马速都大于田忌剩余马中速度最大的
    
26.                 for(i=0;i<c;i++)//遍历田忌的马
    
27.                 {
    
28.                         for(j=temp+1;j<c;j++)//每次必定比掉一场
    
29.                         {
    
30.                                 if(tj[i] > gw[j]) //tj的马若遇到比他小的最大值则直接比掉
    
31.                                 {
    
32.                                         win++;
    
33.                                         temp=j;
    
34.                                         break;
    
35.                                 }
    
36.                                 else if(tj[i] == gw[j]) //势均力敌
    
37.                                 {
    
38.                                         for(k=j+1;k<c;k++)
    
39.                                         {
    
40.                                                 if(tj[i] > gw[k]) break;
    
41.                                         }
    
42.                                         if(k!=c) //平局之后还有比tj小的马
    
43.                                         {
    
44.                                                 win++;
    
45.                                                 temp=k;
    
46.                                         }
    
47.                                         else //平局之后全部等于tj速度最大的马
    
48.                                         {
    
49.                                                 ave++;
    
50.                                             temp=j;
    
51.                                         }
    
52.                                         break;
    
53.                                 }
    
54.                         }
    
55.                         if(j==c) //已经比到国王的最慢的马了
    
56.                         {
    
57.                                 break;
    
58.                         }
    
59.                 }
    
60.                 printf("%d\n",(2*win-c+ave)*200);//赢的场数-输的场数
    
61.         }
    
62.         return 0;
    
63. }

复制代码

不知为何，总有几个测试点过不去，望大佬指点

萨西摩尔·槿花

isdkz 发表于 2023-4-8 19:52
你的代码逻辑是正确的，但是在处理平局情况时存在一些问题。

在平局时，你应该选择让田忌最慢的马与国王 ...

在遍历中，我已默认让tj最小的马去换gw最大的马，即temp之前的已经算作失败了（这里可能可以对tj后temp匹马做些简化）。
在你的代码中，判定平局后直接从tj下一匹马开始遍历，或许忽略了当前tj这匹马在gw的这匹马之后的情况：是全都平局，还是有可能胜出。
感谢