HDU 1052 田忌赛马

今天药忘吃喽~ 2022-04-16 04:58 176阅读 0赞

## 原题目链接[HDU1052][] ##

--------------------

## 分类 ##

HDU 贪心

--------------------

## 题意 ##

**贪心专题**  
**田忌赛马**(不知道上网搜一下回来)  
每次输入一个n代表马匹数，下一行输出田忌每一匹马的数值，然后是王的马匹数值。田忌赢一局得200，输一局扣200，求田忌最多能赚多少。

## 样例输入输出 ##

Sample Input

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

Sample Output

200
    0
    0

--------------------

## 想法 ##

这题首先想到的是贪心，问题是怎么贪呢？假如田忌最好的马比王最好的马好，那就用田忌最好的马和王最好的马比（因为田忌这匹马是稳赢的，当然要打倒最强的对手才能让后面多赢）。如果田忌最好的马比齐王的差，那就用最差的和齐王最好的比。如果田忌和齐王最好的一样强？这时就比较最差的，若是田忌最差的比齐王的差，那就拿去和齐王最好的比；若是比齐王最差的强，那就和齐王最差的比（注意：这时候不应和齐王最强的比，因为这会导致本来可以是一胜一平的变成一胜一负）

--------------------

## 代码 ##

31ms

#include<iostream>
    #include<algorithm>
    using namespace std;
    int main()
    { 
        int tian[1000],king[1000];
        int n;
        while(cin>>n&&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];
            }
            int t1=0,t2=n-1,k1=0,k2=n-1;
    //t1、t2分别是田忌最差和最好的马，k1、k2是齐王的。
            int sum=0;
            sort(tian,tian+n);
            sort(king,king+n);
            for(int i=0;i<n;i++)
            { 
    //田忌最好的马能赢齐王最好的马
                if(tian[t2]>king[k2])
                { 
                    sum+=200;t2-=1;k2-=1;
                }
    //田忌最好的马比不过给齐王最好的马，用田忌最弱的和齐王比
                else if(tian[t2]<king[k2])
                { 
                    sum-=200;t1+=1;k2-=1;
                }
    //最好的马一样强
                else if(tian[t2]==king[k2]&&tian[t1]<king[k1])
                { 
                    sum-=200;t1+=1;k2-=1;
                }
                else if(tian[t2]==king[k2]&&tian[t1]>king[k1])
                { 
                    sum+=200;t1+=1;k1+=1;
                }
                else if(tian[t2]==king[k2]&&tian[t1]==king[k1])
                { 
                    if(tian[t1]<king[k2])sum-=200;//这里注意，可能出现田忌和王的马全一样的情况(样例第二个，这里需要判断一下)
                    t1+=1;k2-=1;
                }
            }
            cout<<sum<<endl;
        }
        return 0;
    }

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