http://acm.hdu.edu.cn/showproblem.php?pid=1052
問題描述
這是中國歷史上的一個著名故事茵瘾。
“那是大約2300年前砸讳。田吉將軍是齊國的一位高級官員慨代。他喜歡與國王和其他人打賽馬焦辅【ジ眨”
“田和國王都擁有三匹不同級別的賽馬毙芜，分別是常規(guī)賽，加賽和超級賽窒朋。規(guī)則是每場比賽要進(jìn)行三輪比賽搀罢；每匹馬都必須使用一輪。單打冠軍 回合從失敗者那里拿走了兩百銀元侥猩±浦粒”
“作為國家最有權(quán)力的人，國王的馬匹非常好欺劳，以至于每班他的馬匹都比田人的馬更好唧取。結(jié)果，國王每次從田人那里拿走六百銀元划提》愕埽”
“田吉對此感到不滿，直到他遇到了中國歷史上最著名的將軍之一孫斌鹏往。由于孫先生的小把戲淡诗，田吉在下一場比賽中帶回家了兩百銀元和如此豐厚的一筆。 ”
“這是一個相當(dāng)簡單的把戲伊履。使用他的普通級賽馬與國王對抗超級類韩容，他們肯定會輸?shù)暨@一回合。但是唐瀑，他的加值擊敗了國王的常規(guī)者群凶，而他的超級也擊敗了國王的加成。這是一個簡單的技巧 那么您如何看待中國的高級官員田吉哄辣？”
如果田吉生活在當(dāng)今请梢，他一定會嘲笑自己赠尾。 更重要的是，如果他現(xiàn)在正參加ACM競賽毅弧，他可能會發(fā)現(xiàn)賽馬問題可以簡單地看作是在二分圖中找到最大匹配項(xiàng)萍虽。 一側(cè)畫田的馬，另一側(cè)畫國王的馬形真。 只要Tian的一匹馬能擊敗國王的一匹杉编，我們就會在它們之間劃出一條優(yōu)勢，這意味著我們希望建立這對咆霜。 然后邓馒，贏得盡可能多的回合的問題僅僅是在此圖中找到最大匹配。 如果存在平局蛾坯，問題變得更加復(fù)雜光酣，他需要為所有可能的邊分配權(quán)重0、1或-1脉课，并找到最大加權(quán)的完美匹配... 但是救军，賽馬問題是二分匹配的一種非常特殊的情況。 該圖由馬的速度決定-較高速度的頂點(diǎn)總是比較低速度的頂點(diǎn)好倘零。 在這種情況下唱遭，加權(quán)二分匹配算法是解決該問題的過于先進(jìn)的工具。 在這個問題中呈驶，要求您編寫一個程序來解決這種特殊的匹配問題拷泽。
輸入項(xiàng)
輸入最多包含50個測試用例。 每種情況在第一行以正整數(shù)n（n <= 1000）開頭袖瞻，這是每一側(cè)的馬數(shù)司致。 第二行中的后n個整數(shù)是田馬的速度。 然后聋迎，第三行的下n個整數(shù)是國王的馬匹速度脂矫。 輸入的最后一行在最后一個測試用例之后以0結(jié)束。
輸出量
對于每種輸入情況霉晕，輸出包含單個數(shù)字的行庭再，這是Tian Ji將獲得的最大金額（以銀元為單位）。
樣本輸入
3 92 83 71 95 87 74 2 20 20 20 20 2 20 19 22 18 0
樣本輸出
200 0 0
問題分析
這是一道很經(jīng)典的貪心算法入門題娄昆。 這道題貪心的思想是 要把每一匹馬的作用發(fā)揮到最大佩微，把已方贏的概率增加到最大
我是從雙方慢馬的角度來分析的缝彬，其實(shí)快馬和慢馬的思路差不多萌焰。
用田忌最慢的馬與王最慢的馬相比較
-
如果田忌的慢馬比王的慢馬要快
果斷把先用田忌的慢馬先贏一把（這樣贏是代價最小的）
-
如果田忌的慢馬比王的慢馬要慢
果斷把這匹慢馬與王最快的馬比賽（因?yàn)榉凑家敚@樣我輸?shù)膬r值更大谷浅，因?yàn)槲野炎羁斓鸟R比下去了扒俯，可以增加后面其他馬贏的機(jī)會）
-
如果田忌的慢馬與王的慢馬速度一樣
-
拿田忌最快的馬和王最快的馬比較
如果田忌快馬比王快馬快奶卓，那就拿這匹快馬贏一局，之所以需要判斷是因?yàn)槲蚁胱屛易盥鸟R收益更大撼玄，如果我的快馬比王的快馬快就沒必要讓慢馬和這匹快馬比了夺姑，我可以直接贏一盤。然后讓我最慢的馬去和王的一匹比我剩下所有的馬都要快的馬比賽掌猛，這樣我的慢馬收益才是最大的盏浙。
如果田忌快馬比王快馬慢，那就拿田忌最慢的馬與王最快的馬比賽荔茬，這樣的話我可以增加已方后面的馬贏的概率废膘，因?yàn)槟惆炎羁斓鸟R拉走了。
-
AC代碼如下慕蔚。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 用來把馬排序丐黄，速度由低到高
double cmp(double a, double b){
return a < b;
};
int main(){
int N;
while(cin>>N && N != 0){
vector<double> tj_horses;
vector<double> king_horse;
for(int i = 0;i < N; i++){
double temp;
cin>>temp;
tj_horses.push_back(temp);
}
for(int i = 0;i < N; i++){
double temp;
cin>>temp;
king_horse.push_back(temp);
}
// 排序田忌和王的馬
sort(tj_horses.begin(), tj_horses.end(), cmp);
sort(king_horse.begin(), king_horse.end(), cmp);
// 下面四個變量用來記錄當(dāng)前田忌和王最快的馬和最慢的馬的位置。左邊為慢馬孔飒，右邊為快馬
int king_left_index = 0;
int king_right_index = N - 1;
int tj_left_index = 0;
int tj_right_index = N - 1;
int tj_money = 0;
for(int i = 0; i < N; i++){
// 如果田忌的慢馬比王的慢馬快灌闺，就先贏一局
if(tj_horses[tj_left_index] > king_horse[king_left_index]){
tj_money+=200;
king_left_index++;
tj_left_index++;
}
// 如果田忌的慢馬與王的慢馬一樣快
else if(tj_horses[tj_left_index] == king_horse[king_left_index]){
// 如果田忌的快馬比王的快馬快，就贏一局
if(tj_horses[tj_right_index] > king_horse[king_right_index]){
tj_money+=200;
tj_right_index--;
king_right_index--;
}
// 如果田忌的快馬比王的快馬慢坏瞄，就輸一局用田忌的慢馬把王的快馬比下去
else{
tj_horses[tj_left_index] < king_horse[king_right_index] ? tj_money-=200 : tj_money = tj_money;
tj_left_index++;
king_right_index--;
}
}
// 如果田忌的慢馬比王的慢馬慢桂对，就輸一局，把王最快的馬比下去
else if(tj_horses[tj_left_index] < king_horse[king_left_index]){
tj_money-=200;
tj_left_index++;
king_right_index--;
}
}
cout<<tj_money<<endl;
}
return -1;
}
