当前位置: 首页 > news >正文

【华为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

题目 又到了一年的末尾&#xff0c;项目组让小明负责新年晚会的小礼品发放工作。为使得参加晚会的同时所获得的小礼品价值相对平衡&#xff0c;需要把小礼品根据价格进行分组&#xff0c;但每组最多只能包括两件小礼品&#xff0c;并且每个分组的价格总和不能超过一个价格上限。…...

[go 面试] 构建高效微服务通信:选择合适的通信方式

关注公众号【爱发白日梦的后端】分享技术干货、读书笔记、开源项目、实战经验、高效开发工具等&#xff0c;您的关注将是我的更新动力&#xff01; 构建分布式系统或微服务架构时&#xff0c;服务间通信成为至关重要的一环。不同的通信方式各有优劣&#xff0c;因此在选择时需根…...

【华为OD题库-048】拔河比赛-java

题目 公司最近准备进行拔河比赛&#xff0c;需要在全部员工中进行挑选。选拔的规则如下: 1.按照身高优先、体重次优先的方式准备比赛阵容 2.规定参赛的队伍派出10名选手 请实现一个选拔队员的小程序。 输入为一个数组&#xff0c;记录了部门人员的身高、体重信息&#xff0c;如…...

【WebSocket】通信协议基于 node 的简单实践和心跳机制和断线重连的实现

前后端 WebSocket 连接 阮一峰大佬 WebSocket 技术博客 H5 中提供的 WebSocket 协议是基于 TCP 的全双工传输协议。它属于应用层协议&#xff0c;并复用 HTTP 的握手通道。它只需要一次握手就可以创建持久性的连接。 那么什么是全双工呢&#xff1f; 全双工是计算机网络中的…...

【有ISSN、ISBN号!往届均已完成EI检索】第三届电子信息工程、大数据与计算机技术国际学术会议(EIBDCT 2024)

第三届电子信息工程、大数据与计算机技术国际学术会议&#xff08;EIBDCT 2024&#xff09; 2024 3rd International Conference on Electronic Information Engineering, Big Data and Computer Technology 第三届电子信息工程、大数据与计算机技术国际学术会议&#xff08;…...

【Windows】使用SeaFile搭建本地私有云盘并结合内网穿透实现远程访问

1. 前言 现在我们身边的只能设备越来越多&#xff0c;各种智能手机、平板、智能手表和数码相机充斥身边&#xff0c;需要存储的数据也越来越大&#xff0c;一张手机拍摄的照片都可能有十多M&#xff0c;电影和视频更是按G计算。而智能设备的存储空间也用的捉襟见肘。能存储大量…...

Windows本地搭建WebDAV服务并使用内网穿透远程访问【无公网IP】

windows搭建WebDAV服务&#xff0c;并内网穿透公网访问【无公网IP】 文章目录 windows搭建WebDAV服务&#xff0c;并内网穿透公网访问【无公网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 开发技术&#xff1a;后端 ssm 后台管理 vue 用户端 vue.jshtml 演示视频&#xff1a; 基于ssm品牌会员在线商城源码 DROP TABLE IF EXISTS address; /*!40101 SET saved_cs_client character_set_client */; /…...

骨传导耳机音量大了有害吗?骨传导能保护听力吗?

无论是传统耳机还是骨传导耳机&#xff0c;只要使用音量过大&#xff0c;都会对有一定的损伤&#xff0c;然而由于骨传导耳机的传声原理和佩戴方式比较特殊&#xff0c;所以对人体的损伤比较小&#xff0c;想要知道骨传导耳机能否保护听力&#xff0c;就要先了解骨传导耳机的传…...

百望云供应链协同解决方案入选北大创新评论产业研究案例库

11月28日-29日&#xff0c;百望云受邀出席《北大创新评论》2023 Inno China 中国产业创新大会&#xff0c;从战略构建、生态塑造、科技创新等议题出发&#xff0c;与学术专家、产业专家、企业代表共赴盛会&#xff0c;思享汇聚。会上&#xff0c;《北大创新评论产业研究案例库&…...

selenium中元素定位正确但是操作失败,6种解决办法全搞定

selenium中元素定位正确但是操作失败的原因无外乎以下4种&#xff1a; 01 页面没加载好 解决方法&#xff1a;添加等待方法&#xff0c;如&#xff1a;time.sleep() 02 页面提交需要等待给数据后台 解决方法&#xff1a;添加等待方法&#xff0c;如&#xff1a;time.sleep(…...

触控板绘画工具Inklet mac功能介绍

Inklet mac是一款触控板绘画工具&#xff0c;把你的触控板变成画画的板子&#xff0c;意思是&#xff0c;你点在触控板的哪里&#xff0c;鼠标就会出现载相应的地方。例如&#xff0c;但你把手指移动到触控盘左下角&#xff0c;那么鼠标也会出现在左下角&#xff0c;对于用户而…...

〔005〕虚幻 UE5 像素流多用户部署

✨ 目录 ▷ 为什么要部署多用户▷ 开启分发服务器▷ 配置启动多个信令服务器▷ 配置启动客户端▷ 多用户启动整体流程和预览▷ 注意事项 ▷ 为什么要部署多用户 之前的像素流部署&#xff0c;属于单用户&#xff0c;是有很大的弊端的打开多个窗口访问&#xff0c;可以看到当一…...

11. 哈希冲突

上一节提到&#xff0c;通常情况下哈希函数的输入空间远大于输出空间&#xff0c;因此理论上哈希冲突是不可避免的。比如&#xff0c;输入空间为全体整数&#xff0c;输出空间为数组容量大小&#xff0c;则必然有多个整数映射至同一桶索引。 哈希冲突会导致查询结果错误&#…...

12.04 二叉树中等题

513. 找树左下角的值 给定一个二叉树的 根节点 root&#xff0c;请找出该二叉树的 最底层 最左边 节点的值。 假设二叉树中至少有一个节点。 示例 1: 输入: root [2,1,3] 输出: 1 思路&#xff1a;找到最低层中最左侧的节点值&#xff0c;比较适合层序遍历&#xff0c;返回最…...

Redis的安装

本文采用原生的方式安装Redis&#xff0c;Redis的版本为5.0.5 安装 下载 下载网站&#xff1a;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 语言的软件开发工具包&#xff0c;主要用于移动设备、嵌入式设备上的java应用程序。JDK是整个java开发的核心&#xff0c;它包含了JAVA的运行环境&#xff08;JVMJava系统类库&#xff09;和JAVA工具。 JDK包含的基本组件包括&#xff1a; javac – 编译器&#xf…...

漫谈HBuilderX App-Jenkins热更新构建

漫谈Uniapp App热更新包-Jenkins CI/CD打包工具链的搭建 零、写在前面 HBuilderX是DCloud旗下的IDE产品&#xff0c;目前只提供了Windows和Mac版本使用。本项目组在开发阶段经常需要向测试环境提交热更新包&#xff0c;使用Jenkins进行CD是非常有必要的一步。尽管HBuilderX提…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

Golang——9、反射和文件操作

反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一&#xff1a;使用Read()读取文件2.3、方式二&#xff1a;bufio读取文件2.4、方式三&#xff1a;os.ReadFile读取2.5、写…...