【题目描述】

钟神近来编码劳累，想骑车风光一番，于是找某君骑自行车比赛。已知某君和钟神的每辆自行车的速度，钟神赢一场得50银两银子，输一场赔50银两，平局不挣也不赔。钟神可以随意安排高中低档自行车的出场数序，假设钟神体力无限无损耗求钟神最多能挣多少钱。

【输入描述】

多行测试数据，每行包含一个整数n和2n个32位正整数，第一个n表示自行车的数量，

之后的n个32位整数表示某君自行车的速度，

最后的n个32位整数表示钟神的自行车的速度

【输出描述】

钟神可以随意安排自行车的出场数序。输出钟神最多能挣多少钱，结果一定在32位整数的范围内

【样例输入】

3 2 1 3 2 2 3
3 2 1 3 1 1 3

【样例输出】

50
0

【参考代码】

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
   int a[1100],b[1100];
   int n;
   while(cin>>n&&n)
   {
       for(int i=0;i<n;i++)
       {
           cin>>a[i];
       }
       for(int j=0;j<n;j++)
       {
           cin>>b[j];       
            
       }
       sort(a,a+n);
       sort(b,b+n);
       int count=0;
       int money=0;
       for(int i=0,j=0;i<n;)
       {
           if(a[i]<b[j])
           {
               i++;
               j++;
               //count++;
               money+=50;
           }
           else
           {
               i++;
           }
       }
       cout<<money<<endl;
        
        
   }
   return 0;
     
}

这是一个典型的贪心算法问题，类似于田忌赛马的策略。目标是通过合理安排钟神和某君的自行车出场顺序，使得钟神的总盈利最大化。每场比赛的规则如下：

• 钟神的自行车速度 > 某君的自行车速度：钟神赢得50银两。

• 钟神的自行车速度 < 某君的自行车速度：钟神输掉50银两。

• 钟神的自行车速度 = 某君的自行车速度：平局，不盈利不亏损。

解题思路

1. 排序：首先将某君和钟神的自行车速度分别排序。排序的目的是为了后续的贪心匹配策略。

• 某君的自行车速度数组 a 按升序排序。

• 钟神的自行车速度数组 b 按升序排序。

2. 贪心策略：

• 如果 b[j] > a[i]，说明钟神的当前自行车可以赢某君的当前自行车，因此盈利增加50银两，同时移动两个指针 i++ 和 j++。

• 如果 b[j] <= a[i]，说明钟神的当前自行车无法赢某君的当前自行车，此时应该用钟神的最慢自行车去消耗某君的当前自行车（类似于田忌赛马中的“用下等马对上等马”策略），因此只移动 i++，不移动 j。

• 使用两个指针 i 和 j 分别指向某君和钟神自行车速度数组的起始位置。

• 比较 a[i] 和 b[j]：

• 这样做的目的是尽可能多地让钟神的自行车赢得比赛，同时避免不必要的损失。

3. 边界情况：

• 如果所有钟神的自行车速度都小于某君的自行车速度，则钟神无法盈利，总盈利为0。

• 如果所有钟神的自行车速度都大于某君的自行车速度，则钟神可以赢得所有比赛，总盈利为 n * 50。