杭电赛马题题解

e third line are the speeds of the king’s horses. The input ends with a line that has a single 0 after the last test case.
Output
For each input case, output a line containing a single number, which is the maximum money Tian Ji will get, in silver dollars.
Sample Input
3
92 83 71
95 87 74
2 20 20
20 20
2 2
0 19
22 18
0
Sample Output
200
0
0

终于遇到一道值得题解报告的题了，这是道贪心的题，在杭电提交了13次10次是WA, 仔细想想，觉得还是思考的方向不对后来百度了下终于大彻大悟，百度上的基本是用C++实现，自己用C语言写了个，先来算法吧：
题目大意：田忌和国王赛马，给出马的数量n，然后是田忌的n匹马，国王的n匹马。问田忌最多可以赢得多少比赛（一场200块）。

因为比赛的时候，是国王先出马，然后田忌再出，田忌有主动权上的优势。
先对田忌和国王的马进行排序。
贪心的策略：
一、当田忌最快的马比国王最快的马快时，用田忌最快的马赢国王最快的马。
二、当田忌最快的马比国王最快的马慢时，用田忌最慢的马输给国王最快的马。
三、当田忌最快的马跟国王最快的马一样快时，分情况：
1、当田忌最慢的马比国王最慢的马快，那么用田忌最慢的马赢国王最慢的马
2、当田忌最慢的马比国王最慢的马慢，那么用田忌最慢的马输给国王最快的马
3、当田忌最慢的马跟国王最慢的马相等的时候，用田忌最慢的马跟国王最快的马比
下面是网上的证明：
证明一、：假设现在国王最快的马是K，田忌最快的马是T，如果存在一种更优的比赛策略，让T的对手不是K，而使得田忌赢更多的钱的话，那么设此时K的对手是t，T的对手是k：( T>K &&T>t && K>k)
1、 若t>K，则有T>k，t>K。这个结果和T>K，t>k是相同的。
2、 若k<t≤K，则有T>k，t≤K。这个结果不如T>K，t>k来得优秀。
3、 若t≤k≤K，则有T>k，t≤K。这个结果和T>K，t≤k是相同的。
由此可知，交换各自对手后，一定不会使得结果变劣，那么假设是不成立的。

证明二、：因为田忌最快的马比国王最快的马慢，所以田忌所有的马都比国王最快的马慢，也就是说此时田忌的所有马都赢不了国王的马，而出于贪心的思想，应该保留相比之下更快的马，因此用最慢的马去输一定不会比用别的马去输来得劣。
其实上面这两个很容易就想得到，最难的是相等的时候。因为不可以直接让田忌最快的马跟国王最快的马打平，或者直接用最慢的马去输给国王最快的马。（存在反例）

下面是我的代码：

#include&l
t;stdio.h>
void swap(int *a,int *b)
{
int temp= *a;
(*a) = (*b);
(*b) = temp;
}
int main()
{
int n,i,k,mina,maxa,sum,maxb,minb;