学步园

题目链接：http://acm.tju.edu.cn/toj/showp1188.html

这是一道比较考验算法的题目，背景是我们非常熟悉的田忌赛马问题，但是在这里确是让我们给出一个解决一般性的田忌赛马问题，即随便给出n组田忌和齐威王的马的速度来求田忌能够胜出的最多盘数，当然，在这道题里面是指田忌这个大财主最多能拿到多少银币。这道题的算法说起来简单，但是也不好想，其实就三句话：

一：如果田忌的最快的马比齐威王最快的马快，则用它来比，先赢一场；

二：如果田忌的最慢的马比齐威王最慢的马快，也用它来比，先赢一场；

三：如果不同于前两种情况的任何一种情况都是用田忌的最慢的马来和齐威王最快的马比；先输一场，这叫懂得取舍~~

当然，这些最快和最慢的名号都是经过不断变化的，每一轮比赛下来之后，跑过的马都不能上场了，我们就当它们跑残了吧==

大家好好想想，其实网上还有好多种情况，但是我认为用我的第三种情况就能涵盖它们所说的除了一二种情况以外的其他各种情况。好了，不废话了，给代码吧。

#include<iostream>
#include<algorithm>
using namespace std;
bool ran(int x,int y)
{
 

   return x<y;
}
int main()
{
   int    k,i,j;
   while(cin>>k)
    {
                if(k==0) break;
                int tj[1001],king[1001];
                for(i=0;i<k;i++)cin>>tj[i];
                for(i=0;i<k;i++)cin>>king[i];
                sort(tj,tj+k,ran);
                sort(king,king+k,ran);
                long int count=0;
                int tj_min=0,tj_max=k-1;
                int king_min=0,king_max=k-1;
                while(tj_min<=tj_max)
                {
                                     if(tj[tj_max]>king[king_max])
                                     {
                                           count++;
                                           tj_max--;king_max--;
                                     }
                                     else if(tj[tj_min]>king[king_min])
                                     {
                                           count++;
                                           tj_min++;king_min++;
                                     }
                                     else
                                     {
                                           if(tj[tj_min]<king[king_max])
                                           count--;
                                           tj_min++;king_max--;
                                     }   
                }
                cout<<count*200<<endl;
    }
   
    return0;
}

原文链接：http://blog.sina.com.cn/s/blog_91f0f71c01016e46.html