hello今天我们又见面了✌话不多说开始吧题目描述田忌和齐王各有 n 匹马每匹马都有一个整数速度值。一次比赛恰好进行 n 局每一局双方各派出一匹尚未出场的马因此每匹马都恰好出场一次。如果田忌的马速度更快田忌获得 200 银币如果两匹马速度相同本局收益为 0如果齐王的马速度更快田忌失去 200 银币。田忌知道双方所有马的速度并可以重新安排自己的出场顺序。等价地他可以在两组马之间选择一种一一配对。请计算田忌能够获得的最大总收益。输入包含若干组比赛数据。输入格式每组数据的第一行包含一个正整数 n表示双方各有 n 匹马。第二行包含 n 个整数表示田忌的马的速度。第三行包含 n 个整数表示齐王的马的速度。所有数据之后有一行单独的整数 0表示输入结束。这个 0 不是一组比赛数据。输出格式对于每组数据输出一行一个整数表示田忌最多能获得多少银币。输入样例 13 92 83 71 95 87 74 0输出样例 1200样例说明田忌可以让速度为 92 的马战胜速度为 87 的马让速度为 83 的马战胜速度为 74 的马再让速度为 71 的马输给速度为 95 的马。总收益为 200200−200200。数据范围对于每组比赛数据1≤n≤2000每匹马的速度均为 0 到 100 的整数。数据特征表中每一行表示对于前 x% 的测试数据该行列出的条件同时成立。#includebits/stdc.h using namespace std; int n,a[2005],b[2005],ans; int main(){ while(1){ ans0; cinn; if(n0)return 0; for(int i1; in; i) cina[i]; for(int i1; in; i) cinb[i]; sort(a1,a1n); sort(b1,b1n); int x11,x21,d1n,d2n; while(x1d1){ if(a[d1]b[d2]){ ans; d1--; d2--; } else{ if(a[x1]b[x2])ans,x1,x2; else if(a[x1]b[d2])x1,d2--; else ans--,x1,d2--; } } coutans*200endl; } return 0; }题解题意与数学模型对每组数据田忌和齐王各有 nn 匹马每匹马都必须恰好出场一次。田忌可以重排自己的出场顺序因此一个合法方案等价于在两组马之间建立一个一一配对。设田忌的速度为 a1,…,ana1​,…,an​齐王的速度为 b1,…,bnb1​,…,bn​。定义一局的单位收益为w(x,y) \begin{cases} 1,xy,\\ 0,xy,\\ -1,xy.b_r$让双方最快马比赛田忌得到 $200$。 2. 否则若 $a_lb_l$让双方最慢马比赛田忌得到 $200$。 3. 否则让田忌最慢马 $a_l$ 对阵齐王最快马 $b_r$。若 $a_lb_r$田忌失去b_r$则 $a_r$ 能战胜齐王所有尚未使用的马。考虑任意一个最优配对设其中 $a_r$ 与 $b_j$ 配对而 $b_r$ 与 $a_i$ 配对。 把这两对改成 $(a_r,b_r)$ 和 $(a_i,b_j)$。前后 $a_r$ 都获胜又因为 $b_j\le b_r$同一匹 $a_i$ 对阵更慢的 $b_j$ 时结果不会比对阵 $b_r$ 更差。交换不会降低总收益所以第一种选择安全。 ### 最慢马可以取胜时 若第一种情况不成立而 $a_lb_l$那么齐王最慢马 $b_l$ 会输给田忌所有尚未使用的马。设某个最优配对中 $b_l$ 与 $a_i$ 配对而 $a_l$ 与 $b_j$ 配对。 交换为 $(a_l,b_l)$ 和 $(a_i,b_j)$ 后对 $b_l$ 的胜局仍然保留。由于 $a_i\ge a_l$用 $a_i$ 代替 $a_l$ 对阵同一匹 $b_j$结果也不会变差。因此第二种选择同样可以出现在某个最优解中。 ### 其余情况可以牺牲最慢马 进入第三种情况时同时有 $a_r\le b_r$ 和 $a_l\le b_l$。田忌最慢马不可能战胜任何尚未使用的齐王马而齐王最快马也不可能被任何田忌马战胜。 在某个最优配对中设 $a_l$ 与 $b_j$ 配对$b_r$ 与 $a_i$ 配对。若 $a_lb_j$那么a_l$则交换后 $a_i$ 能战胜 $b_j$新增的胜局足以补偿 $a_l$ 从平局变成失败。若 $a_lb_r$由排序关系可知所有剩余速度都相同任意配对都为平局。 因此第三种选择也不会排除所有最优解。 三个分支都能确定一对属于某个最优解的马。删去该对后剩余数组仍然有序且问题形式不变。对剩余马匹数量归纳可知算法得到的总收益就是全局最大收益。 ## 实现细节 - 四个指针分别指向两个有序数组的左右端点每轮恰好删除双方各一匹马。 - 第三个分支只有在 $a_l