题意略。
思路：
田忌赛马。经典贪心。分别将田忌和齐王的马排序，设田忌最快和最慢的马分别为f1和s1，齐王的是f2和s2。
共有五种情况：1、f1 > f2，则有f1对阵f2，能赢齐王最快的马，当然是不二选择；
2、f1 < f2，则用s1和f2相比，因为肯定不能赢，用最慢的马去输代价最小；
3、f1=f2, s1 > s2，则s1与s2比赛，既然最慢的马能赢，没有必要浪费更快的马；
4、f1=f2, s1 < s2，则s1对抗f2，最慢的马肯定输，输给最快的马也算输得其所；
5、f1=f2，s1=s2，仍用s1对阵f2，这要证明。
显然，最优方案中，s1要么和f2比，要么和s2比。假设最优匹配是s1与s2配，x与f2配，交换s1和x，所得结果一定不会变差。因为：
若x < f2, 交换后有s1 < f2，x>=s2，可见结果没有变差；若x = f2，则交换后为s1=f2, x=s2或者s1 < f2, x > s2，二者结果都一样。
代码如下：
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 using namespace std; 6 const int maxn = 1005; 7 8 int king[maxn],general[maxn],n; 9 int f0,l0,f1,l1; 10 11 int main(){ 12 while(scanf("%d",&n) == 1 && n){ 13 for(int i = 0;i < n;++i) scanf("%d",&general[i]); 14 for(int i = 0;i < n;++i) scanf("%d",&king[i]); 15 16 sort(general,general + n); 17 sort(king,king + n); 18 reverse(general,general + n); 19 reverse(king,king + n); 20 21 int ans = 0; 22 23 f0 = f1 = 0; 24 l0 = l1 = n - 1; 25 while(f0 <= l0){ 26 if(general[f0] > king[f1]){ 27 ++ans; 28 ++f0; 29 ++f1; 30 } 31 else if(general[f0] < king[f1]){ 32 --ans; 33 --l0; 34 ++f1; 35 } 36 else{ 37 if(general[l0] > king[l1]){ 38 ++ans; 39 --l0; 40 --l1; 41 } 42 else{ 43 ans -= (general[l0] < king[f1] ? 1 : 0); 44 --l0; 45 ++f1; 46 } 47 } 48 } 49 printf("%d\n",ans * 200); 50 } 51 return 0; 52 }
原文：https://www.cnblogs.com/tiberius/p/11509763.html