【华为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提…...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
基于ASP.NET+ SQL Server实现(Web)医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...
SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...
如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)
前言: 最近在做行为检测相关的模型,用的是时空图卷积网络(STGCN),但原有kinetic-400数据集数据质量较低,需要进行细粒度的标注,同时粗略搜了下已有开源工具基本都集中于图像分割这块,…...
Java编程之桥接模式
定义 桥接模式(Bridge Pattern)属于结构型设计模式,它的核心意图是将抽象部分与实现部分分离,使它们可以独立地变化。这种模式通过组合关系来替代继承关系,从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...
uniapp 小程序 学习(一)
利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 :开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置,将微信开发者工具放入到Hbuilder中, 打开后出现 如下 bug 解…...
