【贪心】田忌赛马

点击量: 65 次

题目描述

田忌准备和齐王赛马,各自拿出的比赛马匹数是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;
}

有空再更动态规划算法。

 【双向宽度搜索】九宫重排
简单高精度加法 
上一篇:【双向宽度搜索】九宫重排
下一篇:简单高精度加法


点击开始摧毁这篇水文,方向键控制,空格发弹,Esc退出


pao.gifchui.gifpen.gifpai.gifhan.pngxia.pnghuaji.pngwa.pngbi.pngxin.pngleng.pnghua.pngmeng.pngjingya.pngqian.pnghan1.pngquan.pngnu.pnggan.pngdaxiao.pngku.pngqu.png



Proudly published with Typecho))).

Living (*>ω<*)

Copyright @ 2019 Kira's Blog



哎呀,穷死了,求赞赏!

支付宝
微信
QQ
0:00