【贪心】田忌赛马


题目描述

田忌准备和齐王赛马,各自拿出的比赛马匹数是n个,胜负由每匹马的速度决定,田忌可以自由选择自己的马和齐王的比赛,田忌赢一次赏金加50,输一次赏金赔50,田忌赚的钱最低为0,求田忌最多能赚多少钱?
输入
多行测试数据,每行包含一个整数n和2n个正整数,第一个n表示比赛马的数量,之后的n个整数表示齐王马的速度,此行最后n个整数表示田忌马的速度。
样例输入
3 2 1 3 2 2 3
3 2 1 3 1 1 3
样例输出
50
0

分析

  1. 如果田忌的最快马快于齐王的最快马,则两者比赛一场。这是因为若是田忌的别的马可能就赢不了,所以两者比赛。
  2. 如果田忌的最快马慢于齐王的最快马,则用田忌的最慢马和齐王的最快马比赛一场。这是因为所有的马都赢不了齐王的最快马,所以用损失最小的,拿最慢的和他比。
  3. 若田忌的最快马和齐王的最快马一样快,则比较田忌的最慢马和齐王的最慢马。分成两种情况:
    (1)若田忌的最慢马快于齐王的最慢马,田忌的最慢马和齐王的最慢马比。因为田忌的最慢马既然能赢一个就赢一个,而且齐王的最慢马肯定也得有个和它比,所以选比齐王的最慢马快的最慢马与其比,避免浪费。
    (2)否则就拿田忌的最慢马和齐王的最快马比。因为反正所有的马都比田忌的最慢马快,所以这匹马必输,选贡献最大的比掉齐王的最快马。

AC代码

#include <iostream>
#include <algorithm>
using namespace std;
int cmp(const int a, const int b)
{
    return a < b;
}
int main(void)
{
    int n;
    while(cin>>n)
    {
        int a[100]={0}, b[100]={0}, min1=0, min2=0, max1=n-1, max2=n-1, res=0, cnt=0;
        for(int i=0; i<n; i++)
        cin>>a[i];
        for(int i=0; i<n; i++)
        cin>>b[i];
        sort(a, a+n, cmp);
        sort(b, b+n, cmp);
        while((cnt++)<n)
        {
            if(b[max2]>a[max1])
            {
                res += 50;
                max1--;
                max2--;
            }
            else if(b[max2]<a[max1])
            {
                res -= 50;
                max1--;
                min2++;
            }
            else
            {
                if(b[min2]>a[min1])
                {
                    res += 50;
                    min1++;
                    min2++;
                }
                if(b[min2]<a[min1])
                {
                    res -= 50;
                    min1--;
                    min2--;
                }
            }
        }
        cout<<res<<endl;
    }
    return 0;
}

有空再更动态规划算法。

声明:Kira's Blog|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - 【贪心】田忌赛马


Truth is I missed those summer days