博客

难度：4

这道题比较好写，好些在数据只有2000，可以用n的平方来写，贪心的思路就比较简单了，齐王的马要从大到小排，但是田忌的马不用，然后遍历齐王的马，从田忌的马里面找处比齐王马大，但是大的最小的马来应对，就可以了，然后就是细节，处理完之后先统计田忌能赢多少，然后去统计平局多少，这里就用到了两个散列数组，来解决，

#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pa;

const int N = 2005;

bool cmp(int a, int b) {
    return a > b;
}

int main() {
    int n;
    cin >> n;
    int a[N], b[N];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    sort(b, b + n, cmp);
    int Hash[N] = {};
    int Hash2[N] = {};
    for (int i = 0; i < n; i++) {
        int last_pos = -1;
        int temp = 0x7fffffff;
        for (int j = 0; j < n; j++) {
            if (Hash[j] == 0) {
                if (a[j] > b[i] && a[j] - b[i] < temp) {
                    temp = a[j] - b[i];
                    if (last_pos != -1) Hash[last_pos] = 0;
                    last_pos = j;
                    Hash[j] = 1;
                    Hash2[i] = 1;
                }
            }
        }
    }
    int x1 = 0;
    for (int i = 0; i < n; i++) {
        if (Hash[i]) x1++;
    }
    int x2 = 0;
    for (int i = 0; i < n; i++) {
        if (Hash2[i]) continue;
        for (int j = 0; j < n; j++) {
            if (Hash[j] == 0) {
                if (a[j] == b[i]) {
                    x2++;
                    Hash[j] = 1;
                    break;
                }
            }
        }
    }
    n -= x2;
    cout << 200 * (x1 * 2 - n);
    return 0;
}