HDU-1052 Tian Ji -- The Horse Racing
题面
就是一个实现设计田忌式赛马策略的程序
总结
因为题目里有这么一句话，让我迷惑了好一会儿：
In this case, the weighted bipartite matching algorithm is a too advanced tool to deal with the problem.
在这种情况下，加权二分匹配算法是解决该问题的过于先进的工具。
加权二分匹配？
实际上题目十分明显地告诉了你这其实是田忌赛马题（这标题不就是田忌赛马吗？我还饶有兴致地看完了英文版的背景描述）。我们只需要按照田忌的策略完成这道题就可以了。
简单来说，就是（按照顺序进行比较，满足了就结束比较，否则继续看下一条）：
- 如果田忌的最慢的马跑得比大王 最慢的马快，那么田忌就使用这匹马跟大王最慢的马比赛（最慢的马都能跑过又怎么能为了一匹最慢的马浪费了一匹快马呢？）；
- 如果田忌的最慢的马跑得比大王 最慢的马慢，那么田忌就要勇敢些，将这匹最慢的马拿去和大王最快的马比赛（反正这匹马怎么弄都是输还不如让他去消耗掉大王最快的马）！
- 如果田忌 最快的马跑得比大王 最快的马要快，那么田忌需要用这匹马去跟大王最快的马比赛，获得胜利的机会（别的马又不一定行，拿这匹马跟慢马比赛就是浪费）！
- 如果田忌 最快的马跑得比大王 最快的马要慢，田忌需要用最慢的那匹马与大王最快的马比赛，浪费掉大王的快马，为自己争取胜利的机会！
- 如果田忌 最快的马跑得比大王 最快的马一样快，那么就拿最慢的那匹马去和王最快的马比赛，平局的代价跟后面输一局后大王的快马没有田忌的快马快，赢过来差不多。
AC代码
#include<bits/stdc++.h>
using namespace std;
int tmp,n,ans;
deque<int> tian,king;
int main (){
while(1){
scanf("%d",&n);
if(n==0)return 0;
tian.clear();king.clear();ans=0;
for(int i=1;i<=n;i++){
scanf("%d",&tmp);
tian.push_back(tmp);
}sort(tian.begin(),tian.end(),greater<int>());
for(int i=1;i<=n;i++){
scanf("%d",&tmp);
king.push_back(tmp);
}sort(king.begin(),king.end(),greater<int>());
while(n){
if(tian.back()>king.back()){
ans++;tian.pop_back();
king.pop_back();n--;
}else if(tian.back()<king.back()){
ans--;tian.pop_back();
king.pop_front();n--;
}else if(tian.front()>king.front()){
ans++;tian.pop_front();
king.pop_front();n--;
}else if(tian.front()<king.front()){
ans--;tian.pop_back();
king.pop_front();n--;
}else if(tian.back()>king.front()){
ans++;tian.pop_back();
king.pop_front();n--;
}else if(tian.back()<king.front()){
ans--;tian.pop_back();
king.pop_front();n--;
}else{
tian.pop_back();
king.pop_front();n--;
}
}
printf("%d\n",ans*200);
}
}