MorsLin 的博客

MorsLin 的博客

前事不忘,后事之师

题解 P1650 【田忌赛马】

posted on 2019-01-20 08:50:44 | under 题解 |

题目传送门

贪心好题,原题应为LA3266


首先给国王和田忌的马从小到大排序

接下来是贪心策略:

  1. 首先比最快的马,如果能赢就直接赢
  2. 如果赢不了,就比国王和田忌最慢的马,能赢就赢
  3. 如果最慢的马也赢不了,就用最慢的马去怼国王最快的马

为什么这么做是对的呢?

首先,如果我方最快的马能赢对方最快的马,肯定要赢,这不难理解
如果赢不了,那有两种情况,一种是平,一种是输
如果输了,反正也是输,我当然要保留实力,用最菜的马去输,这也不难理解
但如果平了,怎么办?
此时,单纯的比一端并不能保证最优策略

国王 田忌
4 4
3 3
2 2
1 1

比如这样,用最慢的马去输给国王,可以换来之后的全胜。显然这样更优
所以我们可以先比最慢的马,能赢的话就赢,因为它还有价值,不用去给最快的马当炮灰。
如果赢不了,就把它送出去,浪费对方的好马。

Code

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
const int MAXN = 2010;
using namespace std;
int read(){
    int k = 0; char c = getchar();
    while(c < '0' || c > '9')
      c=getchar();
    while(c >= '0' && c <= '9')
      k = k * 10 + c - 48, c = getchar();
    return k;
}
int king[MAXN], tian[MAXN], ans;
bool cmp(int x, int y){
    return x > y;
}
int main() {
    int n = read(), t, h, tot;
    t = n, tot = h = 1;
    for(int i = 1; i <= n; i++) tian[i] = read();
    for(int i = 1; i <= n; i++) king[i] = read();
    sort(tian+1, tian+n+1, cmp);
    sort(king+1, king+n+1, cmp);
    while(h <= t){
        if(tian[h] > king[tot]) //最快的马能赢
          ans += 200, ++h, ++tot;
        else if(tian[h] < king[tot]) //最快的马赢不了
          ans -=200, --t, ++tot;
        else if(tian[t] > king[n]) //最快的马打平,比较最慢的马
            --t, --n, ans+=200;
        else ans -= tian[t] == king[tot] ? 0 : 200, --t, ++tot;
    }
    cout << ans;
    return 0;
}