【题目描述】

钟神近来编码劳累，想骑车风光一番，于是找某君骑自行车比赛。已知某君和钟神的每辆自行车的速度，钟神赢一场得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。