hdu-1052Tian Ji — The Horse Racing(田忌赛马)

发布于 2019-07-19  1.34k 次阅读


问题传送门:

题意:

田忌赛马,两个人,每个人有 n 匹马, 给出每匹马的速度。
赢一场得200分,输一场减 200 分。
问田忌最多能得多少分。(第一行是田忌)

分析:

是非常经典的贪心问题,只是这个最优策略并不像故事中那么简单。

首先,将两人的马 降序 排列。 分别用两个头指针两个尾指针,方便进行操作。

(1)如果 田忌 最快的马 比 对手最快的马快,直接比,赢一场,两个头指针加加。

(2)如果 田忌 最快的马 比 对手最快的马慢,那肯定是要输一场的,就拿田忌最慢的马

去和对手最快的马比。

(3)如果两人最快的马的速度相同,先不要着急去打平局。此时再看最慢的马。

                <1>如果最慢的马比对手最慢的马快,直接比,赢一场。
                <2>如果最慢的马比对手最慢的马慢,这个最慢的马肯定要输一场,和对手最快的马去比赛。
                这样同样是输,又消耗了对手一个最快的马。
                <3>如果两人最慢的马的速度也相同,,也拿最慢的和对手最快的比较,此时要注意的是
                 会不会两人的马的速度都相同。



代码:
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long LL;

const int MAXN = 1100;

int a[MAXN];
int b[MAXN];

bool cmp(int a, int b)
{
    return a > b;
}

int main()
{
    int n;
    while (cin >> n && n)
    {
        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);
        int sj = 0, ej = n-1;
        int sw = 0, ew = n-1;
        int win = 0;

        while(sj <= ej && sw <= ew)
        {
            if (a[sj] > b[sw])
            {
                win++;
                sj++, sw++;
            }
            else if (a[sj] < b[sw]){
                win--;
                ej--, sw++;
            } 
            else 
            { // 当两者最快的马相等时    
                if (a[ej] > b[ew]){
                    win++;
                    ej--, ew--;
                } 
                else if (a[ej] < b[ew]) {
                    win--;
                    ej--, sw++;
                }
                else {
                    if (a[ej] < b[sw])
                        win--;
                    ej--, sw++;
                }
            }
        }
        cout << win*200 << endl;
    }
    return 0;
}

Simple And Clear