hdu 1052 Tian Ji -- The Horse Racing【田忌赛马】

题目

这道题主要是需要考虑到各种情况：先对马的速度进行排序，然后分情况考虑：

1.当田忌最慢的马比国王最慢的马快则赢一局

2.当田忌最快的马比国王最快的马快则赢一局

3.当田忌最快的马比国王最快的马慢 则用田忌最慢的马和国王最快的马比，输一局

4.当他们最快的马相等时则用 田忌最慢的马和国王最快的马比。【因为自己后面的队友很有可能战胜此时对方的这匹慢马，所以就算自己输一场，队友也能帮忙赢回一场，而胜一场，输一场的收益和打平一场的收益是一样的，而且自己输的时候可以拉对方最快的马下水，给己方最快的马创造更大的胜利机会，也就是说己方最快的马很可能因为自己的牺牲再胜利一场，从这个角度看，还是自己故意输掉比较好。举个列子：

Tian： 3 6 8

King：3 7 9。如果Tian的3和King的3打平手，那么Tian会输2场；Tian的3打King的9，Tian赢2场；

】

#include<iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

int main()

{

  int n;

  int Tian[1110],King[1110];

  while(cin>>n)

  {

      if(n==0) break;

      for(int i=0;i<n;i++)

        cin>>Tian[i];

      for(int i=0;i<n;i++)

          cin>>King[i];

     sort(Tian,Tian+n);

     sort(King,King+n);

     int sj=0,sk=0;

     int ej=n-1,ek=n-1;

     int ans = 0;

     for(int i=0;i<n;i++)

     {

         if(Tian[sj]>King[sk]){//Tian(min)>King(min)

            ans++;

            sj++;sk++;

         }else if(Tian[ej]>King[ek]){//Tian(max)>King(max)

            ans++;

            ej--;ek--;

         }else if(Tian[ej]<King[ek]){//Tian(max)<King(max)

            ans--;

            sj++;

            ek--;

         }else if(Tian[ej]==King[ek]){//Tian(max)=King(max)

                if(Tian[sj]<King[ek])

                    ans--;

                sj++;

                ek--;

         }

     }

     cout<<ans*200<<endl;

  }

    return 0;

}