算法题(94):除2!

devtools/2025/3/13 13:15:37/

审题:

本题需要我们对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!


http://www.ppmy.cn/devtools/166777.html

相关文章

AI科技公司招聘一位后端开发工程师

招聘岗位:后端开发工程师(兼运维) 公司名称:深圳市格子科技有限公司 公司介绍:深圳市格子科技有限公司作为AI应用创新先锋,构建起以AI工具研发为核心、短剧平台运营为延伸的多业务发展模式。公司自主研发A…

linux在 Ubuntu 系统中设置服务器时间

在 Ubuntu 系统中设置服务器时间通常涉及以下步骤,涵盖自动同步和手动配置两种方式。以下是详细操作指南: 一、检查当前时间状态 timedatectl status输出示例:Local time: Wed 2023-10-18 15:30:00 UTC Universal time: Wed 2023-10-18 15:3…

51单片机Proteus仿真速成教程——P1-软件与配置+Proteus绘制51单片机最小系统+新建程序模版

前言:本文主要围绕 51 单片机最小系统的绘制及程序模板创建展开。首先介绍了使用 Proteus 绘制 51 单片机最小系统的详细步骤,包括软件安装获取途径、工程创建、器件添加(如单片机 AT89C51、晶振、电容、电阻、按键等)、外围电路&…

【蓝桥杯速成】| 1.暴力解题

1高频考点与暴力解题_哔哩哔哩_bilibili 感谢up主分享,以下内容是学习笔记,以c为主,部分python 题目一:维纳的年龄 题目内容 美国数学家维纳(N.Wiener)智力早熟, 11岁就上了大学。他曾在1935~1936年应邀来中国清华大…

反射、 Class类、JVM的类加载机制、Class的常用方法

DAY11.1 Java核心基础 反射 重点和难点,应用面很广 大部分库和框架都需要用到反射机制,它是动态语言的关键,但是概念抽象不好理解 反射:通过实例化类映射到类,从而获取类的信息 概括说就是:常规情况是…

scrcpy pc机远程 无线 控制android app 查看调试log

背景: 公司的安卓机,是那种大屏幕的连接usb外设的。不好挪动,占地方,不能直接连接pc机上的android stduio来调试。 所以从网上找了一个python adb.exe控制器,可以局域网内远程控制开发的app,并在android stduio上看…

2024年广州市智能网联汽车创新实践年度报告

政策法规方面,积极推进《广州市智能网联汽车创新发展条例》的制定和发布,不断完善法规标准体系,为产业创新发展营造良好政策环境;技术创新方面,企业加大研发投入,在自动驾驶算法、车联网安全等关键领域取得…

【架构艺术】Go语言微服务monorepo的代码架构设计

近期因为项目架构升级原因,笔者着手调研一些go项目monorepo的代码架构设计,目标是长期把既有微服务项目重要的部分都转移到monorepo上面,让代码更容易维护,协作开发更加方便。虽然经验不多,但既然有了初步的调研&#…