Luogu P1650 田忌赛马

题目传送门

贪心好题，原题应为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;
}