10.22 解题报告

T1

用时：约 \(30\) min

首先不难发现，若干个人组成的集合 \(A\) 若满足条件的话，当且仅当对于每一个元素 \(A_i\)，都有 \(b_{A_i}\le \sum a_{A_j}-a_{A_i}\)，也即 \(b_{A_i}+a_{A_i}\le \sum a_{A_j}\)。

所以可以考虑枚举左边的 \(a_i+b_i\) 的最大值，贪心的去找 \(a\) 值最大的，计数，取 \(\min\) 即可，复杂度 \(O(n^2\log n)\) 可以得到 \(60\) pts。

发现上面的贪心找 \(a\) 最大的方案每次都要排序，非常的浪费，考虑能不能用一些数据结构来进行维护。

考虑使用 STL 中的 multiset 来实现，初始将所有元素插入，枚举 \(a_i+b_i\) 的最大值时需要实现单个元素的删除，此时判断一下当前这个 \(a_i\) 在上一次有没有被选中，如果有，就再加一个未选择的最大值进去，否则不管，再来判断是否符合条件。

如果符合，一直减掉最大的选中的元素，直至不符合，此时更新答案。

如果不符合，此次答案一定不会更优，直接忽略。

注意到 multiset 中的指针整体是单调移动的，所以单次操作复杂度均摊 \(O(\log n)\)，总复杂度是 \(O(n \log n)\)。

原文地址：http://www.cnblogs.com/wapmhac/p/16823877.html