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)\)。
标签:10.22,le,log,报告,复杂度,元素,解题,最大值 From: https://www.cnblogs.com/wapmhac/p/16823877.html