您的位置:首页 > 财经 > 金融 > 专业的教育行业网站制作_重庆市建设工程信息网官网网址_seo排名赚app靠谱吗_福州短视频seo公司

专业的教育行业网站制作_重庆市建设工程信息网官网网址_seo排名赚app靠谱吗_福州短视频seo公司

2025/9/10 19:29:22 来源:https://blog.csdn.net/2301_79954395/article/details/146217388  浏览:    关键词:专业的教育行业网站制作_重庆市建设工程信息网官网网址_seo排名赚app靠谱吗_福州短视频seo公司
专业的教育行业网站制作_重庆市建设工程信息网官网网址_seo排名赚app靠谱吗_福州短视频seo公司

审题:

本题需要我们对n个数据中的偶数数据进行不大于k次除2操作,使得n个数据的总和最小

思路:
方法一:贪心与优先级队列(大堆)

贪心策略:我们每次都对目前最大的偶数进行除2的操作

策略证明:由于我们的奇数不可以进行操作,所以不考虑,然后偶数中,越大的数据除2,所造成的数据值减少越大,所以每次都对目前最大的偶数除2就可以达到全局最小

解题:

(1)第一步:将奇数先直接加入sum中,偶数先放进数组中

sum用longlong是为了方式数据太大存不下

(2)第二步:利用优先级队列把数组数据按照大堆排列,从而可以确保每次都对最大偶数操作

使用大堆可以用比暴力查找更少的时间完成最大数据的提取,其实本题也可以解释为查找前k个最大偶数,不过这前k个是动态的

基本逻辑:对最大偶数除2,若为奇数,弹出堆并加入sum中

若为偶数,弹出原数据,然后插入除2后的数据

注意:

1.while循环需要保证队列中还有数据,否则后面的top会有问题

2.对于最大偶数除2后的数据无论如何都要删除

分类1:变成了奇数,奇数无法进行除2操作,自然要删除

分类2:变成了偶数,如果不删除,那么后续我们插入除2后的数据就会导致数据冗余了

(3)第三步:操作k次后,如果还有数据存储在队列中,将剩下的数据加上即可

除2!

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com