1052 Tian Ji -- The Horse Racing

题目详情： 

Tian Ji -- The Horse Racing

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 47942    Accepted Submission(s): 14651

题目大意：

田忌和国王赛马看谁的马快，匹数均为n，田忌每赢国王一局，+200元，输一局-200元，平局+0元，

问如何安排比赛马的出场比赛顺序可以使田忌尽可能多赢钱。

 解题思路：

先把田忌的马和国王的马分别降序排序，如果田忌的快马比国王的快马快，则胜局+1，否则，

拿田忌的慢马和国王的慢马比较，慢马能赢就赢，如果田忌的慢马输了再拿田忌的慢马和国王的快马进行比较，这里贪心比较明显，用自己最慢的马去浪费对方最快的马，反正走到这步肯定没有马可以跑赢对面的快马，干脆拿慢马去消耗掉一个比赛的机会。

AC代码：

#include<bits/stdc++.h>
using namespace std;
bool cmp(int a,int b){return a>b;
}
int main(){int n;//每次双方各有多少匹马int horse;//马(用于输入)while(cin>>n&&n!=0){vector<int> tianji;//田忌的马vector<int> king;//皇帝的马int sum_win=0;//田忌赢的场数int tianji_fast=0;//田忌的快马int tianji_slow=n-1;//田忌的慢马int king_fast=0;//国王的快马int king_slow=n-1;//国王的慢马for(int i=0;i<n;++i){cin>>horse;tianji.push_back(horse);}for(int i=0;i<n;++i){cin>>horse;king.push_back(horse);}sort(tianji.begin(),tianji.end(),cmp);//降序排序sort(king.begin(),king.end(),cmp);//降序排徐for(int i=0;i<n;++i){if(tianji[tianji_fast]>king[king_fast]){//田忌的快马赢++tianji_fast;//田忌下一匹快马++king_fast;//国王下一匹快马++sum_win;//赢的次数+1}//执行到这说明田忌的快马没有国王的快马快else if(tianji[tianji_slow]>king[king_slow]){//田忌的慢马比国王的慢马快--tianji_slow;//田忌的上一匹慢马--king_slow;//国王的上一匹慢马++sum_win;//赢的次数+1}//执行到这说明田忌的慢马没有国王的慢马快else if(tianji[tianji_slow]<king[king_fast]){//田忌的慢马比国王的快马慢--tianji_slow;//田忌的上一匹慢马++king_fast;//国王的下一匹快马--sum_win;//输了,赢的次数-1}}cout<<sum_win*200<<endl;//输出}return 0;
}