有一个比较经典的田忌赛马贪心策略:让己方最弱和对方最强比赛。但是这种策略会出现问题,比如己方为 4,5,6,7,敌方为 3,4,5,6,按照刚才的策略结果是三胜一负,但显然最优情况是四胜。因此本题不能用田忌赛马的策略来贪心。
如果己方最弱可以打过敌方最弱,那么没必要把它送给敌方最强。如果己方最弱打不过敌方最弱或平局,应该把己方最弱送给敌方最强。如果己方最强打得过敌方最强,也没有必要让己方最弱和敌方最强比赛。
因此正确的贪心策略如下:
-
判断己方最弱能否战胜敌方最弱,若能则这样安排,若不能进入步骤 2
-
判断己方最强能否战胜敌方最强,若能则这样安排,若不能进入步骤 3
-
判断己方最弱是否能和敌方最强打成平局。
由于己方和敌方的分数加起来是定值,所以己方最坏情况就是敌方的最优情况,把敌方当成己方算即可,即
#include <bits/stdc++.h>
using namespace std;
int n, a[200010], b[200010];
int solve(int *a, int *b) {
int L1 = 1, R1 = n;
int L2 = 1, R2 = n;
int ans = 0;
while (L1 <= R1 && L2 <= R2) {
if (a[L1] > b[L2]) {
ans = ans + 2;
L1++;
L2++;
} else if (a[R1] > b[R2]) {
ans = ans + 2;
R1--;
R2--;
} else {
if (a[L1] == b[R2])
ans++;
L1++;
R2--;
}
}
return ans;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
sort(b + 1, b + 1 + n);
printf("%d %d\n", solve(a, b), 2 * n - solve(b, a));
return 0;
}