员题

【题意简述】

双方各有 $n$ 匹马，每匹马具有一个速度。两边的马一一比赛，胜、平、负的收益分别为 $1,0,-1$，求最大总收益。

【Hint】

【提示】

将双方速度分别排序。若最快马可以获胜，就固定最快马之间的比赛；否则尝试固定最慢马之间的胜局；两种胜局都不存在时，用最慢马消耗对方最快马。

【数据点 1∼21\sim 21∼2】

枚举双方马匹之间的全部双射，再计算每一种安排的收益。时间复杂度为 $\mathcal{O}(n!n)$，空间复杂度为 $\mathcal{O}(n)$。

这个做法的瓶颈在于同时确定了全部配对。如果能证明某一场比赛一定可以出现在最优方案中，就可以逐场固定答案。

【数据点 3∼43\sim 43∼4】

先用插入排序将两组速度升序排列，再执行正解中的两端贪心。时间复杂度为 $\mathcal{O}(n^2)$，空间复杂度为 $\mathcal{O}(n)$。

【正解】

将双方速度序列分别记为 $a,b$。排序后维护 $l_a,r_a,l_b,r_b$，表示双方尚未参赛的最慢马与最快马。

1. 若 $a_{r_a}>b_{r_b}$，让两匹最快马比赛，答案加一。
2. 否则，若 $a_{l_a}>b_{l_b}$，让两匹最慢马比赛，答案加一。
3. 否则，让 $a_{l_a}$ 与 $b_{r_b}$ 比赛。若 $a_{l_a}<b_{r_b}$，答案减一；相等时答案不变。

下面分别证明三种选择均不会使答案变劣。

第一种情况中，设某个最优方案让 $a_{r_a}$ 对阵 $b_j$，让 $a_k$ 对阵 $b_{r_b}$。交换这两场的对手后，$a_{r_a}$ 仍然获胜；又因为 $b_j\leq b_{r_b}$，$a_k$ 对阵 $b_j$ 的结果不会比原来更差。因此存在一个最优方案包含最快马之间的配对。

第二种情况中，设某个最优方案让 $a_{l_a}$ 对阵 $b_j$，让 $a_k$ 对阵 $b_{l_b}$。交换后 $a_{l_a}$ 可以战胜 $b_{l_b}$；又因为 $a_k\geq a_{l_a}$，$a_k$ 对阵 $b_j$ 的结果不会比 $a_{l_a}$ 对阵 $b_j$ 更差。因此也存在一个最优方案包含最慢马之间的配对。

最后只剩 $a_{r_a}\leq b_{r_b}$ 且 $a_{l_a}\leq b_{l_b}$。此时 $a_{l_a}$ 无法战胜任何剩余对手，$b_{r_b}$ 也不会输给任何剩余的马。设原方案中 $a_{l_a}$ 对阵 $b_j$，$a_k$ 对阵 $b_{r_b}$。交换后，若原来两场都失败，收益显然不会低于 $-2$；若恰有一场平局，$a_k$ 对阵更慢的 $b_j$ 至少平局，总收益仍不下降；若两场都是平局，则交换后仍为两场平局，或得到一胜一负。因此可以让最慢马消耗对方最快马。

每一步都固定了某个最优方案中的一场比赛，重复这一过程即可得到全局最优解。

【复杂度分析】

排序需要 $\mathcal{O}(n\log n)$ 的时间，四个指针均只会单向移动。总时间复杂度为 $\mathcal{O}(n\log n)$，空间复杂度为 $\mathcal{O}(n)$。

【参考代码】

1#include <cstdio>2#include <algorithm>3#define MAXN 10000104using namespace std;5 6int c,n,LineA[MAXN],LineB[MAXN];7 8int main() {9#ifndef ONLINE_JUDGE10    freopen("race.in","r",stdin);11    freopen("race.out","w",stdout);12#endif13    scanf("%d",&c);14    scanf("%d",&n);15    for (int i=1;i<=n;i++) scanf("%d",&LineB[i]);16    for (int i=1;i<=n;i++) scanf("%d",&LineA[i]);17    sort(LineA+1,LineA+n+1);18    sort(LineB+1,LineB+n+1);19    int LeftA=1,RightA=n,LeftB=1,RightB=n,Ans=0;20    while (LeftA<=RightA) {21        if (LineA[RightA]>LineB[RightB]) {22            Ans++;23            RightA--;RightB--;24        }25        else if (LineA[LeftA]>LineB[LeftB]) {26            Ans++;27            LeftA++;LeftB++;28        }29        else {30            if (LineA[LeftA]<LineB[RightB]) Ans--;31            LeftA++;RightB--;32        }33    }34    printf("%d\n",Ans);35    return 0;36}