【华为OD题库-062】计算礼品发放的最小分组数目-java
题目
又到了一年的末尾,项目组让小明负责新年晚会的小礼品发放工作。为使得参加晚会的同时所获得的小礼品价值相对平衡,需要把小礼品根据价格进行分组,但每组最多只能包括两件小礼品,并且每个分组的价格总和不能超过一个价格上限。为了保证发放小礼品的效率,小明需要找到分组数目最少的方案。
你的任务是写一个程序,找出分组数最少的分组方案,并输出最少的分组数目。
输入
第一行数据为分组礼品价格之和的上限
第二行数据为每个小礼品的价格,按照空格隔开,每个礼品价格不超过分组价格和的上限
输出
输出最小分组数量
示例1:
输入:
5
1 2 5
输出:
2
思路
最多只能分两个礼品,要求最小方案数。先将输入nums按从小到大排序,以数据为例:1 2 3 3 5 8(假设不超过8),让left指向第一个礼物1,right指向最后一个礼物8
计算当前礼物价值:8+1=9,超过限制,8只能单独分一组,right- -,res=1
left=1,right=5,和为6,可以分为一组,left++,right- -,res=2
left=2,right=3,可以分为一组,left++,right- -,res=3
left=3,right=3,指向的同一个值,单独分一组即可,res=4
上述过程可以用队列或者双指针模拟实现。
题解
package hwod;import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;public class GiftGroup {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int max = sc.nextInt();sc.nextLine();int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();System.out.println(giftGroup(nums, max));System.out.println(giftGroup2(nums, max));}private static int giftGroup(int[] nums, int max) {Arrays.sort(nums);LinkedList<Integer> queue = new LinkedList<>();for (int num : nums) {queue.addLast(num);}int res = 0;while (queue.size() > 1) {int cur = queue.peekLast() + queue.peekFirst();queue.removeLast();if (cur <= max) {queue.removeFirst();}res++;}return queue.isEmpty() ? res : res + 1;}private static int giftGroup2(int[] nums, int max) {Arrays.sort(nums);int left = 0, right = nums.length - 1, res = 0;while (left < right) {int cur = nums[right] + nums[left];right--;res++;if (cur <= max) {left++;}}return left==right?res+1:res;}
}
推荐
如果你对本系列的其他题目感兴趣,可以参考华为OD机试真题及题解(JAVA),查看当前专栏更新的所有题目。
相关文章:
【华为OD题库-062】计算礼品发放的最小分组数目-java
题目 又到了一年的末尾,项目组让小明负责新年晚会的小礼品发放工作。为使得参加晚会的同时所获得的小礼品价值相对平衡,需要把小礼品根据价格进行分组,但每组最多只能包括两件小礼品,并且每个分组的价格总和不能超过一个价格上限。…...
[go 面试] 构建高效微服务通信:选择合适的通信方式
关注公众号【爱发白日梦的后端】分享技术干货、读书笔记、开源项目、实战经验、高效开发工具等,您的关注将是我的更新动力! 构建分布式系统或微服务架构时,服务间通信成为至关重要的一环。不同的通信方式各有优劣,因此在选择时需根…...
【华为OD题库-048】拔河比赛-java
题目 公司最近准备进行拔河比赛,需要在全部员工中进行挑选。选拔的规则如下: 1.按照身高优先、体重次优先的方式准备比赛阵容 2.规定参赛的队伍派出10名选手 请实现一个选拔队员的小程序。 输入为一个数组,记录了部门人员的身高、体重信息,如…...
【WebSocket】通信协议基于 node 的简单实践和心跳机制和断线重连的实现
前后端 WebSocket 连接 阮一峰大佬 WebSocket 技术博客 H5 中提供的 WebSocket 协议是基于 TCP 的全双工传输协议。它属于应用层协议,并复用 HTTP 的握手通道。它只需要一次握手就可以创建持久性的连接。 那么什么是全双工呢? 全双工是计算机网络中的…...
【有ISSN、ISBN号!往届均已完成EI检索】第三届电子信息工程、大数据与计算机技术国际学术会议(EIBDCT 2024)
第三届电子信息工程、大数据与计算机技术国际学术会议(EIBDCT 2024) 2024 3rd International Conference on Electronic Information Engineering, Big Data and Computer Technology 第三届电子信息工程、大数据与计算机技术国际学术会议(…...
【Windows】使用SeaFile搭建本地私有云盘并结合内网穿透实现远程访问
1. 前言 现在我们身边的只能设备越来越多,各种智能手机、平板、智能手表和数码相机充斥身边,需要存储的数据也越来越大,一张手机拍摄的照片都可能有十多M,电影和视频更是按G计算。而智能设备的存储空间也用的捉襟见肘。能存储大量…...
Windows本地搭建WebDAV服务并使用内网穿透远程访问【无公网IP】
windows搭建WebDAV服务,并内网穿透公网访问【无公网IP】 文章目录 windows搭建WebDAV服务,并内网穿透公网访问【无公网IP】1. 安装IIS必要WebDav组件2. 客户端测试3. cpolar内网穿透3.1 打开Web-UI管理界面3.2 创建隧道3.3 查看在线隧道列表3.4 浏览器访…...
责任链设计模式
package com.jmj.pattern.responsibility;/*** 请假条类*/ public class LeaveRequest {//姓名private String name;//请假天数private int num;//请假内容private String content;public LeaveRequest(String name, int num, String content) {this.name name;this.num num;…...
12.4 C++ 作业
完成沙发床的多继承 #include <iostream>using namespace std;//封装 沙发 类 class Sofa { private:string *sitting; public://无参构造函数Sofa(){cout << "Sofa::无参构造函数" << endl;}//有参构造函数Sofa(string s):sitting(new string(s)…...
基于ssm品牌会员在线商城源码
基于ssm品牌会员在线商城源码708 idea mysql数据库 navcat 开发技术:后端 ssm 后台管理 vue 用户端 vue.jshtml 演示视频: 基于ssm品牌会员在线商城源码 DROP TABLE IF EXISTS address; /*!40101 SET saved_cs_client character_set_client */; /…...
骨传导耳机音量大了有害吗?骨传导能保护听力吗?
无论是传统耳机还是骨传导耳机,只要使用音量过大,都会对有一定的损伤,然而由于骨传导耳机的传声原理和佩戴方式比较特殊,所以对人体的损伤比较小,想要知道骨传导耳机能否保护听力,就要先了解骨传导耳机的传…...
百望云供应链协同解决方案入选北大创新评论产业研究案例库
11月28日-29日,百望云受邀出席《北大创新评论》2023 Inno China 中国产业创新大会,从战略构建、生态塑造、科技创新等议题出发,与学术专家、产业专家、企业代表共赴盛会,思享汇聚。会上,《北大创新评论产业研究案例库&…...
selenium中元素定位正确但是操作失败,6种解决办法全搞定
selenium中元素定位正确但是操作失败的原因无外乎以下4种: 01 页面没加载好 解决方法:添加等待方法,如:time.sleep() 02 页面提交需要等待给数据后台 解决方法:添加等待方法,如:time.sleep(…...
触控板绘画工具Inklet mac功能介绍
Inklet mac是一款触控板绘画工具,把你的触控板变成画画的板子,意思是,你点在触控板的哪里,鼠标就会出现载相应的地方。例如,但你把手指移动到触控盘左下角,那么鼠标也会出现在左下角,对于用户而…...
〔005〕虚幻 UE5 像素流多用户部署
✨ 目录 ▷ 为什么要部署多用户▷ 开启分发服务器▷ 配置启动多个信令服务器▷ 配置启动客户端▷ 多用户启动整体流程和预览▷ 注意事项 ▷ 为什么要部署多用户 之前的像素流部署,属于单用户,是有很大的弊端的打开多个窗口访问,可以看到当一…...
11. 哈希冲突
上一节提到,通常情况下哈希函数的输入空间远大于输出空间,因此理论上哈希冲突是不可避免的。比如,输入空间为全体整数,输出空间为数组容量大小,则必然有多个整数映射至同一桶索引。 哈希冲突会导致查询结果错误&#…...
12.04 二叉树中等题
513. 找树左下角的值 给定一个二叉树的 根节点 root,请找出该二叉树的 最底层 最左边 节点的值。 假设二叉树中至少有一个节点。 示例 1: 输入: root [2,1,3] 输出: 1 思路:找到最低层中最左侧的节点值,比较适合层序遍历,返回最…...
Redis的安装
本文采用原生的方式安装Redis,Redis的版本为5.0.5 安装 下载 下载网站:https://download.redis.io/releases/ wget http://download.redis.io/releases/redis-5.0.5.tar.gz解压 tar -zxvf redis-5.0.5.tar.gz进入redis目录 cd redis-5.0.5执行编译…...
JDK安装太麻烦?一篇文章搞定
JDK是 Java 语言的软件开发工具包,主要用于移动设备、嵌入式设备上的java应用程序。JDK是整个java开发的核心,它包含了JAVA的运行环境(JVMJava系统类库)和JAVA工具。 JDK包含的基本组件包括: javac – 编译器…...
漫谈HBuilderX App-Jenkins热更新构建
漫谈Uniapp App热更新包-Jenkins CI/CD打包工具链的搭建 零、写在前面 HBuilderX是DCloud旗下的IDE产品,目前只提供了Windows和Mac版本使用。本项目组在开发阶段经常需要向测试环境提交热更新包,使用Jenkins进行CD是非常有必要的一步。尽管HBuilderX提…...
如何通过FCEUX实现NES游戏高精度模拟?解锁经典游戏的数字化体验
如何通过FCEUX实现NES游戏高精度模拟?解锁经典游戏的数字化体验 【免费下载链接】fceux FCEUX, a NES Emulator 项目地址: https://gitcode.com/gh_mirrors/fc/fceux 你是否曾因找不到可靠的NES模拟器而无法重温童年经典游戏?是否遇到过模拟器兼容…...
WSABuilds旧版本归档:如何获取v2311及更早版本安装包
WSABuilds旧版本归档:如何获取v2311及更早版本安装包 【免费下载链接】WSABuilds Run Windows Subsystem For Android on your Windows 10 and Windows 11 PC using prebuilt binaries with Google Play Store (MindTheGapps) and/or Magisk or KernelSU (root solu…...
不用下载IDE!浏览器直接练Python二级考题的宝藏网站测评
浏览器直通Python二级考场:零配置备考实战指南 距离全国计算机二级Python考试还有30天,小张的笔记本电脑却突然罢工。维修店报价让他望而却步,而图书馆公共电脑禁止安装软件的规定更让他雪上加霜。这种困境并非个例——据教育技术协会2024年…...
3步搞定黑苹果配置:OpCore-Simplify让EFI构建效率提升80%的智能方案
3步搞定黑苹果配置:OpCore-Simplify让EFI构建效率提升80%的智能方案 【免费下载链接】OpCore-Simplify A tool designed to simplify the creation of OpenCore EFI 项目地址: https://gitcode.com/GitHub_Trending/op/OpCore-Simplify 你是否经历过这些痛苦…...
手把手教你windows下如何部署copaw
前言: 本文内容主要讲解通过手工部署python并使用pip安装部署copaw,在官网有一键部署脚本等等教程,都很方便,但为什么作者要通过手工部署python环境,原因很简单,解决环境冲突的问题,通过conda能…...
LIBPNG深度解析:构建企业级PNG处理架构的技术决策指南
LIBPNG深度解析:构建企业级PNG处理架构的技术决策指南 【免费下载链接】libpng LIBPNG: Portable Network Graphics support, official libpng repository 项目地址: https://gitcode.com/gh_mirrors/li/libpng LIBPNG作为PNG格式的官方参考实现库࿰…...
PECVD vs 磁控溅射:氮化硅薄膜制备工艺全解析(附击穿场强测试数据)
PECVD与磁控溅射:氮化硅薄膜工艺的深度博弈与性能优化 在半导体器件制造和MEMS传感器领域,氮化硅薄膜作为关键功能材料,其介电性能和结构特性直接影响器件可靠性。当前工业界主要采用等离子体增强化学气相沉积(PECVD)和…...
Cadence Virtuoso IC618版图验证全流程:解决PEX提参map error的详细步骤
Cadence Virtuoso IC618版图验证全流程:解决PEX提参map error的详细步骤 从IC514迁移到IC618的过程就像给老房子换新地基——表面上看功能相似,但底层架构的升级带来了全新的操作逻辑和隐藏的"陷阱"。最近三个月,我团队完成了7个项…...
终极Ghidra安装指南:5分钟在Ubuntu系统快速部署逆向工程神器
终极Ghidra安装指南:5分钟在Ubuntu系统快速部署逆向工程神器 【免费下载链接】ghidra_installer Helper scripts to set up OpenJDK 11 and scale Ghidra for 4K on Ubuntu 18.04 / 18.10 项目地址: https://gitcode.com/gh_mirrors/gh/ghidra_installer 想要…...
all-MiniLM-L6-v2保姆级教程:Ollama模型卸载、版本回滚与缓存清理指南
all-MiniLM-L6-v2保姆级教程:Ollama模型卸载、版本回滚与缓存清理指南 1. 为什么需要管理你的Ollama模型? 你可能已经用Ollama成功部署了all-MiniLM-L6-v2,体验了它轻量高效的句子嵌入能力。但用久了你会发现,硬盘空间在悄悄减少&…...
