收益等于所选项目估值的最小值 m 加上入选个数 k。若固定最小值取某个 x,则为了让 k 尽量大,应把所有不小于 x 的项目都选上。
因此把数组升序排序后,枚举 ai 作为最小值,此时可选个数为 n−i,收益为 ai+(n−i)。遍历取最大即可。
时间复杂度 O(∑nlogn),空间复杂度 O(n)。
投资机构手头有 n 个候选项目,第 i 个项目的估值为 ai。需要选出一个非空子集立项(按下标区分,相同估值也可同时入选)。收益规则由风控给出:所选估值中的最小值,加上入选项目的个数。请计算可能达到的最高收益。
约束:测试组数不超过 102,单组 1≤n≤200000,且所有测试中 n 之和不超过 300000。1≤ai≤1000000000。
第一行一个正整数 T,表示测试组数,满足 1≤T≤102。 对每组测试:第一行一个正整数 n;第二行 n 个正整数 a1,a2,…,an。
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.