4.7小红书笔试 求第二题解法
小红发布n篇笔记,第i篇笔记的点赞数为a_i,评论数为b_i,选取k篇作为合集,合集的优秀程度为合集中笔记的点赞数之和乘以评论数的最小值。求最大的合集优秀程度。
样例:第一行为n,k。第二行为点赞数,第三行为评论数
4 2
1 2 3 4
3 4 2 1
output:
10
样例:第一行为n,k。第二行为点赞数,第三行为评论数
4 2
1 2 3 4
3 4 2 1
output:
10
全部评论
cy
理解乘最小的就行,即你的和再大,你的乘数小,结果也是小。所以先按照评论数从大到小排序,前K个优秀程度就是当前的sum*评论[k-1],后面就是遍历就行,只有当当前的sum会变大的情况下,才考虑计算【因为评论数呈现非递增排序,所以后面的乘数一定是<=当前的】
按评论数从大到小排序 遍历的时候用一个小根堆保存当前最大的k个点赞数
动态规划过73%
相关推荐
点赞 评论 收藏
分享
02-24 19:45
西南大学 后端工程师
程序员小白条:简历写的有点太多了,一般两页是实习经历比较多的情况下,要么自己有一些有影响力的开源项目,如果你走软件,硬件没必要实习,学校安排总是没区分度的,央国企最好有中大厂实习,另外学历比较重要,不是都要求硕士的,技术会比互联网要求低一些 点赞 评论 收藏
分享
查看18道真题和解析