像我这种蒟蒻就非常适合做一些辣鸡题，比如一些简单的贪心题，今天偶遇田忌赛马，于是我就非常轻（费）松（力）地搞定了这道题。 题目：
时间: 1000ms / 空间: 131072KiB
描述
中国古代的历史故事“田忌赛马”是为大家所熟知的。话说齐王和田忌又要赛马了，他们各派出N匹马，每场比赛，输的一方将要给赢的一方200两黄金，如果是平局的话，双方都不必拿出钱。现在每匹马的速度值是固定而且已知的，而齐王出马也不管田忌的出马顺序。请问田忌该如何安排自己的马去对抗齐王的马，才能赢取最多的钱？输入格式
第一行为一个正整数n (n <= 1000) ，表示双方马的数量。 第二行有N个整数表示田忌的马的速度。 第三行的N个整数为齐王的马的速度。
输出格式
仅有一行，为田忌赛马可能赢得的最多的钱，结果有可能为负。 测试样例1
输入
3 92 83 71 95 87 74
输出
200
分析： 很明显的贪心嘛~~~ 首先，双方的马按速度排序。
考虑己方最弱的马和对方最弱的马的速度关系。如果对方更弱，那么不妨就用这匹马去对对方的那匹马；如果我方更弱，那么不妨用这匹马和对方当前最强的马比赛。（平局稍后再说）
同样地，可以考虑己方最强的马和对方最强的马的关系。
不停地贪心处理，直到双方最强的马相等、最弱的马也相等。
这时，强制让这两局平局发生（划掉），用我方最弱的马输给对方最强的马（显然优于划掉的），其实并不一定输，还要比较一下我方最弱的马是否与对方最强的马的速度相等，如果相等，那就不会输了。 继续处理，直到所有的马都用完。
简单吧？！
代码：
#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef double DB; int Max(int a, int b){return a > b ? a : b;} int Min(int a, int b){return a < b ? a : b;} const int MAXN = 1e3 + 15; int a[MAXN], b[MAXN]; inline int read(){ int r = 0, z = 1; char ch = getchar(); while(ch < '0' || ch > '9'){if(ch == '-') z = -1; ch = getchar();} while(ch >= '0' && ch <= '9'){r = r * 10 + ch - '0'; ch = getchar();} return r * z; } bool cmp(int x, int y){return x > y;} void fre(){ freopen(".in", "r", stdin); freopen(".out", "w", stdout); } void init(){ int n = read(), ans = 0; for(int i = 1; i <= n; i ++) a[i] = read(); for(int i = 1; i <= n; i ++) b[i] = read(); sort(a + 1, a + n + 1, cmp); sort(b + 1, b + n + 1, cmp); int h0 = 1, t0 = n, h1 = 1, t1 = n; while(h0 <= t0){ if(a[h0] > b[h1]){ans ++; h0 ++; h1 ++;} else if(a[h0] < b[h1]){ans --; t0 --; h1 ++;} else if(a[t0] > b[t1]){ans ++; t0 --; t1 --;} else if(a[t0] < b[t1]){ans --; t0 --; h1 ++;} else { if(a[t0] < b[h1]){ans --; t0 --; h1 ++;} else if(a[t0] == b[h1]){t0 --; h1 ++;} } } printf("%d\n", ans * 200); } int main(){ // fre(); init(); return 0; }