题解 P1650 【田忌赛马】
MorsLin
2019-01-20 08:50:44
[**题目传送门**](https://www.luogu.org/problemnew/show/P1650)
贪心好题，原题应为[**LA3266**](https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1267)
---
首先给国王和田忌的马从小到大排序
接下来是贪心策略：
1. 首先比最快的马，如果能赢就直接赢
2. 如果赢不了，就比国王和田忌最慢的马，能赢就赢
3. 如果最慢的马也赢不了，就用最慢的马去怼国王最快的马
为什么这么做是对的呢？
首先，如果我方最快的马能赢对方最快的马，肯定要赢，这不难理解
如果赢不了，那有两种情况，一种是平，一种是输
如果输了，反正也是输，我当然要保留实力，用最菜的马去输，这也不难理解
但如果平了，怎么办？
此时，单纯的比一端并不能保证最优策略
| 国王 | 田忌 |
| :---: | :---: |
| 4 | 4 |
| 3 | 3 |
| 2 | 2 |
| 1 | 1 |
比如这样，用最慢的马去输给国王，可以换来之后的全胜。显然这样更优
所以我们可以先比最慢的马，能赢的话就赢，因为它还有价值，不用去给最快的马当炮灰。
如果赢不了，就把它送出去，浪费对方的好马。
Code
```cpp
#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;
}
```