题目
题意
田忌赛马，问最多能赢到多少钱？每局200元
思路
明显，把田忌的赛马排列一下，从速度高到低，齐王的也从高到低排列，当前田忌最高的赛马无法处理齐王最高的赛马，则换成田忌最慢的赛马去碰瓷。
难在如何处理平局-也就是速度相同的赛马。
有的时候本可以平局，但是最好先认输一局-换用目前最慢的赛马去碰瓷一下，然后当前这匹赛马与接下来比它弱的赛马比试，这样做胜一局负一局，收益为0，与直接平局是相同的。但是优点在于额外用田忌的驽马解决了一匹齐王的好马。
那么，何时直接平局，何时解决额外的马呢？
不妨看看目前的驽马，如果当前自己最慢的马还能解决齐王的最慢马，那么优先让这个对局发生。直到自己最慢的马无法解决齐王最慢的马，此时用这匹驽马来额外解决齐王的快马。
感想
1. 一开始只想到越高越好，从高到低直接处理，没有考虑到当前自己最慢的马还能解决齐王的最慢马这种情况，导致没法选择何时应该主动放弃平局。
2. 之后用了DP，太慢
3. 不只处理一端，也处理另一端以理清局面
代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 1e3 + 3;
typedef pair<int, int> Pair;
int a[MAXN];
int b[MAXN];
int n;
int main() {
int T;
//scanf("%d", &T);
freopen("C:\\Users\\Iris\\source\\repos\\ACM\\ACM\\input.txt", "r", stdin);
//freopen("C:\\Users\\Iris\\source\\repos\\ACM\\ACM\\output.txt", "w", stdout);
for (int ti = 1; scanf("%d", &n) == 1 && n; ti++) {
for (int i = 0; i < n; i++) {
scanf("%d", a + i);
}
sort(a, a + n);
for (int i = 0; i < n; i++) {
scanf("%d", b + i);
}
sort(b, b + n);
int ans = 0;
for (int ai = n - 1, astart = 0, bi = n - 1, bstart = 0; ai >= astart && bi >= bstart; ) {
while (bi >= 0 && a[ai] < b[bi]) {
bi--;
ans--;
astart++;
}
if (bi >= 0) {
if (a[ai] > b[bi]) {
ans++;
bi--;
ai--;
}
else {
while (ai >= astart && bi >= bstart && a[astart] > b[bstart]) {
ans++;
astart++;
bstart++;
}
if (ai >= astart && bi >= bstart && a[astart] < b[bi]) {
astart++;
bi--;
ans--;
}
else {
break;
}
}
}
}
printf("%d\n", ans * 200);
}
return 0;
}