2的时候.
a1 a2
b1 b2
因为 田忌最快的马和齐王最快的马相等 所以a1=b1,a2=b2 所以这种情况有2种比赛方式，易得这两种方式得分相等。
2）当数列a和数列b全部相等等时(a1=b1,a2=b2...an=bn)，显然最慢的马来和齐王最快的马比有最优解,可以赢n-1长，输1场，找不到更好的方
法了。
3）当数列a和数列b元素全部相等时(a1=b1=a2=b2...=an=bn)，无法赢也不输。
现在假设n匹马时拿最慢的马来和齐王最快的马比有最优解，证明有n+1匹马时拿最慢的马来和齐王最快的马比也有最优解。
数列
a1 a2 a3 a4...an an+1
b1 b2 b3 b4...bn bn+1
其中ai>=ai-1,bi>=bi-1
数列a和数列b不全部相等时，拿最慢的马来和齐王最快的马比数列得到数列
(a1) a2 a3 a4...an an+1
b1 b2 b3 b4...bn (bn+1)
分4种情况讨论
1.b1=b2,an=an+1
则有
a2 a3 a4...an
b2 b3 b4...bn
其中a2>=a1,a1=b1,b1=b2,得a2>=b2(此后这种大小关系不再论述）,an>=bn.
此时若a2=b1,根据归纳假设，有最优解，否则a2>根据前面“公理”论证有最优解。
当且仅当a数列,b数列元素全部相等时有an+1=b1,已证得，所以an+1>b1，赢回最慢的马来和齐王最快的马比输的那一场。
2.b1<=b2,an=an+1
交换 b1,b2的位置，
数列
(a1) a2 a3 a4...an an+1
b2 b1 b3 b4...bn (bn+1)
此时 a2>=a1,an>=bn,
对于子表
a2 a3 a4...an
b1 b3 b4...bn
根据前面“公理”或归纳假设，有最优解。
an+1>=b2, 当且仅当b2=b3=b4=..=bn+1时有an+1=b2，这种情况，a中其它元素<=b1,b2,b3,b4..bn,对于这部分来说，能赢 x盘(x<=n)，假如不拿最慢的马来和齐王最快的马比则拿最快的马来和齐王最快的马比，此时平一盘，能赢x-1盘，而拿最慢的马来和齐王最快的马 比，输一盘能赢x盘，总的来说，还是X这个数，没有亏。
3.b1=b2,an<=an+1
4.b1<=b2,an<=an+1证明方法类似，不再重复。
以证得当有n+1匹马的时候，田忌和齐王最快最慢的马速度相等时，拿最慢的马来和齐王最快的马比有最优解，已知当n=2时成立，所以对于n>2且为整数（废话，马的只数当然是整数）时也成立。当n=1时....这个似乎不用讨论.
样例：
#include
#include
#include
#include
using namespace std; bool cmp(int a,int b) { return a>b; } int main() { int n,money; int a[1000],b[1000]; while(cin>>n) { if(!n) break; for(int i=0;i
>a[i]; for(int i=0;i
>b[i]; sort(a,a+n,cmp); sort(b,b+n,cmp); money=0; for(int i=n-1;i>=0;i--) { if(a[i]>b[i]) { money++; } else if(a[i]
b[0]) { money++; for(int j=0;j
b[0]) { money++; for(int j=0;j