杭电oj 1052田忌赛马问题

http://acm.hdu.edu.cn/showproblem.php?pid=1052

问题描述

这是中国历史上的一个著名故事。

“那是大约2300年前。田吉将军是齐国的一位高级官员。他喜欢与国王和其他人打赛马。”

“田和国王都拥有三匹不同级别的赛马，分别是常规赛，加赛和超级赛。规则是每场比赛要进行三轮比赛；每匹马都必须使用一轮。单打冠军回合从失败者那里拿走了两百银元。”

“作为国家最有权力的人，国王的马匹非常好，以至于每班他的马匹都比田人的马更好。结果，国王每次从田人那里拿走六百银元。”

“田吉对此感到不满，直到他遇到了中国历史上最著名的将军之一孙斌。由于孙先生的小把戏，田吉在下一场比赛中带回家了两百银元和如此丰厚的一笔。 ”

“这是一个相当简单的把戏。使用他的普通级赛马与国王对抗超级类，他们肯定会输掉这一回合。但是，他的加值击败了国王的常规者，而他的超级也击败了国王的加成。这是一个简单的技巧那么您如何看待中国的高级官员田吉？”

图片

如果田吉生活在当今，他一定会嘲笑自己。更重要的是，如果他现在正参加ACM竞赛，他可能会发现赛马问题可以简单地看作是在二分图中找到最大匹配项。一侧画田的马，另一侧画国王的马。只要Tian的一匹马能击败国王的一匹，我们就会在它们之间划出一条优势，这意味着我们希望建立这对。然后，赢得尽可能多的回合的问题仅仅是在此图中找到最大匹配。如果存在平局，问题变得更加复杂，他需要为所有可能的边分配权重0、1或-1，并找到最大加权的完美匹配... 但是，赛马问题是二分匹配的一种非常特殊的情况。该图由马的速度决定-较高速度的顶点总是比较低速度的顶点好。在这种情况下，加权二分匹配算法是解决该问题的过于先进的工具。在这个问题中，要求您编写一个程序来解决这种特殊的匹配问题。

输入项

输入最多包含50个测试用例。每种情况在第一行以正整数n（n <= 1000）开头，这是每一侧的马数。第二行中的后n个整数是田马的速度。然后，第三行的下n个整数是国王的马匹速度。输入的最后一行在最后一个测试用例之后以0结束。

输出量

对于每种输入情况，输出包含单个数字的行，这是Tian Ji将获得的最大金额（以银元为单位）。

样本输入

3 92 83 71 95 87 74 2 20 20 20 20 2 20 19 22 18 0

样本输出

200 0 0

问题分析

这是一道很经典的贪心算法入门题。这道题贪心的思想是 要把每一匹马的作用发挥到最大，把已方赢的概率增加到最大

我是从双方慢马的角度来分析的，其实快马和慢马的思路差不多。

用田忌最慢的马与王最慢的马相比较

如果田忌的慢马比王的慢马要快

果断把先用田忌的慢马先赢一把（这样赢是代价最小的）
如果田忌的慢马比王的慢马要慢

果断把这匹慢马与王最快的马比赛（因为反正都要输，这样我输的价值更大，因为我把最快的马比下去了，可以增加后面其他马赢的机会）
如果田忌的慢马与王的慢马速度一样
1. 拿田忌最快的马和王最快的马比较
  1. 如果田忌快马比王快马快，那就拿这匹快马赢一局，之所以需要判断是因为我想让我最慢的马收益更大，如果我的快马比王的快马快就没必要让慢马和这匹快马比了，我可以直接赢一盘。然后让我最慢的马去和王的一匹比我剩下所有的马都要快的马比赛，这样我的慢马收益才是最大的。
  2. 如果田忌快马比王快马慢，那就拿田忌最慢的马与王最快的马比赛，这样的话我可以增加已方后面的马赢的概率，因为你把最快的马拉走了。

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);
        // 下面四个变量用来记录当前田忌和王最快的马和最慢的马的位置。左边为慢马，右边为快马
        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;
}