P4653¶

什么叫普及题困了我一个小时？

真是神了，压根没往贪心那方想。。

关于贪心的证明：

假设\(A\)组较小的情况

假设对于某一种选法，有一个\(a_i\)没有选而且大于已经选的\(a_k\)，可知把\(a_k\)换成\(a_i\)会使答案更优。
假设对于某一种选法，有一个\(b_i\)没有选且大于已经选的\(b_k\)，可知把\(b_k\)换成\(b_i\)时\(A\)仍然较小，对答案无影响。
假设对于某一种选法，有一个\(b_i\)没有选且大于已经选中的一部分\(b_n,b_m....\)的和，可知把\(b_n,b_m....\)替换为\(b_i\)会使答案更优。

综上，此时\(A\)组和\(B\)组内均为原各自组中最大的那一批。

\(B\)组较小的情况同理。

所以可以使用双指针，排序后\(A\)中一个指针，\(B\)中一个指针，\(A\)选的越多\(B\)选的不会变少，于是可有解法。