田忌赛马

洛谷-P1650-田忌赛马

实现

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

const int N = 2010;
int n, a[N];
deque<int> t, q; // 田忌、齐威王

int main () {
    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++ i) t.push_back(a[i]);
    for (int i = 1; i <= n; ++ i) cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++ i) q.push_back(a[i]);

    int res = 0;
    while (n --) {
        if (t.back() > q.back()) { // 田忌最好的马赢齐威王最好的马
            t.pop_back();
            q.pop_back();
            res += 200;
        } else if (t.front() > q.front()) { // 田忌最差的马赢齐威王最差的马
            t.pop_front();
            q.pop_front();
            res += 200;
        } else if (t.front() < q.back()) { // 田忌最差的马消耗齐威王最好的马
            t.pop_front();
            q.pop_back();
            res -= 200;
        } else {
            // 平局
        }
    }
    cout << res << endl;
    return 0;
}