田忌赛马

萨西摩尔·槿花

田忌赛马
输入
输入最多包含 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

你的代码逻辑是正确的，但是在处理平局情况时存在一些问题。

在平局时，你应该选择让田忌最慢的马与国王最快的马进行比赛，而不是在平局之后去寻找比田忌当前马速度小的马。这样可以保证田忌更多的赢面。

修改后的代码如下：

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,j,temp,tj[1001]={0},gw[1001]={0};
    
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.                 temp=-1;
    
25.                 for(i=0;i<c;i++)
    
26.                 {
    
27.                         for(j=temp+1;j<c;j++)
    
28.                         {
    
29.                                 if(tj[i] > gw[j])
    
30.                                 {
    
31.                                         win++;
    
32.                                         temp=j;
    
33.                                         break;
    
34.                                 }
    
35.                                 else if(tj[i] == gw[j])
    
36.                                 {
    
37.                                     temp=j;
    
38.                                     break;
    
39.                                 }
    
40.                         }
    
41.                         if(j==c)
    
42.                         {
    
43.                                 break;
    
44.                         }
    
45.                 }
    
46.                 printf("%d\n",(2*win-c)*200);
    
47.         }
    
48.         return 0;
    
49. }

复制代码

这个修改后的代码应该可以通过所有测试点。如果还有问题，请随时提问。

萨西摩尔·槿花

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

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

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

isdkz

萨西摩尔·槿花 发表于 2023-4-8 20:10
在遍历中，我已默认让tj最小的马去换gw最大的马，即temp之前的已经算作失败了（这里可能可以对tj后temp匹 ...

抱歉，我对你的代码理解有误。现在我明白你的思路了。你的方法是尝试让当前的田忌马在平局后找到一个能赢的国王马。这种做法确实可以解决问题，但是效率可能不是很高，特别是在很多平局的情况下。

我建议使用双指针的方法来解决这个问题。这种方法可以确保在每一步都选择最优解。代码如下：

1. #include "stdio.h"
   
2. #include <stdlib.h>
   
3. 
   
4. int compare(const void *a, const void *b)
   
5. {
   
6.     return *(int*)a - *(int*)b;
   
7. }
   
8. 
   
9. int main()
   
10. {
    
11.     int c, i, win, lose, tj_slow, gw_slow, tj[1001] = {0}, gw[1001] = {0};
    
12.     while (scanf("%d", &c) && c != 0)
    
13.     {
    
14.         for (i = 0; i < c; i++)
    
15.         {
    
16.             scanf("%d", &tj[i]);
    
17.         }
    
18.         for (i = 0; i < c; i++)
    
19.         {
    
20.             scanf("%d", &gw[i]);
    
21.         }
    
22.         qsort(tj, c, sizeof(int), compare);
    
23.         qsort(gw, c, sizeof(int), compare);
    
24.         win = 0;
    
25.         lose = 0;
    
26.         tj_slow = 0;
    
27.         gw_slow = 0;
    
28.         for (i = c - 1; i >= 0; i--)
    
29.         {
    
30.             if (tj[i] > gw[i])
    
31.             {
    
32.                 win++;
    
33.             }
    
34.             else if (tj[i] < gw[i])
    
35.             {
    
36.                 lose++;
    
37.                 tj_slow++;
    
38.             }
    
39.             else
    
40.             {
    
41.                 while (tj_slow < c && gw_slow < c)
    
42.                 {
    
43.                     if (tj[tj_slow] > gw[gw_slow])
    
44.                     {
    
45.                         win++;
    
46.                         tj_slow++;
    
47.                         gw_slow++;
    
48.                     }
    
49.                     else
    
50.                     {
    
51.                         if (tj[tj_slow] < gw[gw_slow])
    
52.                         {
    
53.                             lose++;
    
54.                         }
    
55.                         tj_slow++;
    
56.                         gw_slow++;
    
57.                     }
    
58.                 }
    
59.             }
    
60.         }
    
61.         printf("%d\n", (win - lose) * 200);
    
62.     }
    
63.     return 0;
    
64. }

复制代码

双指针方法的基本思想是分别使用两个指针分别遍历田忌的马和国王的马。这种方法可以在每一步都确保选择最优解，而且时间复杂度相对较低。

希望这个解决方案对你有帮助。如果还有问题，请随时提问。

jhq999

1. #include <iostream>
   
2. using namespace std;
   
3. int cmp(const void* a,const void*b)
   
4. {
   
5.     return *(int*)a-*(int*)b;
   
6. }
   
7. int main()
   
8. {
   
9.     int n,i,j,k,w;
   
10.     while(1)
    
11.     {
    
12.         cin>>n;
    
13.         if(0==n)break;
    
14.         int a[n],b[n];
    
15.         for(i=0;i<n;i+=1)
    
16.         {
    
17.             cin>>a[i];
    
18.         }
    
19.         for(i=0;i<n;i+=1)
    
20.         {
    
21.             cin>>b[i];
    
22.         }
    
23.         qsort(a,n,sizeof(int),cmp);
    
24.         qsort(b,n,sizeof(int),cmp);
    
25.         for(i=n-1,j=n-1,w=0;j>=0;j-=1)
    
26.         {
    
27.             if(a[i]>b[j])
    
28.             {
    
29.                 w+=1;
    
30.                 i-=1;
    
31.             }
    
32.             else if(a[i]<b[j])
    
33.             {
    
34.                 w-=1;
    
35.             }
    
36.             else
    
37.                 i-=1;
    
38.         }
    
39. 
    
40.         cout<<w*200<<endl;
    
41.     }
    
42.     return 0;
    
43. }
    

复制代码