Codeforces Round 920 (Div. 3)

赛时过了 A~E ，表现分 1738 。

感觉 D~G 都挺有意义拿出来说的。

[D] Very Different Array

首先一个贪心的猜想是：如果 A 和 B 长度相同，那一个顺序一个逆序应该是最优的情况。

思考下如何证明这个猜想。

假如 A 和 B 的长度均为 2 ，易证 \(A_1\) < \(A_2\) ，\(B_1\) > \(B_2\) 时最优。

把这个结论推广到长度为 n ，那么对于每一个 A 和 B 均顺序的数对，都可通过使 B 逆序的方式得到更大的答案。这样就证完了。

本题就是一个 B 的长度为 m ，比 A 长的情型。

那么还是考虑把 B 倒着放，然后 B 的前 k 个和 A 的前 k 个配对，后 (n - k) 个和 A 的后 (n - k) 个配对即可得到答案。枚举 k 即可。