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

【洛谷贪心算法题】P1094纪念品分组

该题运用贪心算法,核心思想是在每次分组时,尽可能让价格较小和较大的纪念品组合在一起,以达到最少分组的目的。
在这里插入图片描述

【算法思路】

  1. 输入处理:首先读取纪念品的数量n和价格上限w,然后依次读取每件纪念品的价格,并将其存储在容器vector中

  2. 排序:使用 sort 函数对纪念品的价格进行从小到大的排序。排序的目的是方便后续使用双指针法,能快速找到价格最小和最大的纪念品。

  3. 双指针初始化:初始化两个指针 left 和 right,分别指向价格最小和最大的纪念品。同时,初始化分组数量 groups 为 0。

  4. 分组过程:
    ◦ 当 left 小于等于 right 时,进入循环:
    ◦ 如果 left 等于 right,说明只剩下一个纪念品,将分组数量加 1 并跳出循环。
    ◦ 如果价格最小和最大的纪念品价格之和不超过价格上限 w ,则将它们分为一组,left 指针右移一位,right 指针左移一位,分组数量加 1。
    ◦ 如果价格最小和最大的纪念品价格之和超过价格上限 w ,则将价格最大的纪念品单独分为一组,right 指针左移一位,分组数量加 1。

  5. 输出结果:循环结束后,输出分组的数量。

【代码示例】

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main() {int w, n;// 读取每组纪念品价格上限 w 和纪念品数量 ncin >> w;cin >> n;// 使用 n 来初始化 vector 的大小vector<int> P(n);// 读取每个纪念品的价格for (int i = 0; i < n; i++) {cin >> P[i];}// 对纪念品价格从小到大排序sort(P.begin(), P.end());// 双指针法分组int left = 0;int right = n - 1;// 初始化分组数量为 0int groupCount = 0;while (left <= right) {if (left == right) {// 若只剩一个纪念品,单独成一组groupCount += 1;break;}if (P[left] + P[right] <= w) {// 若最小和最大价格的纪念品能分在一组groupCount += 1;left += 1;right -= 1;} else {// 若不能,最大价格的纪念品单独成一组right -= 1;groupCount += 1;}}// 输出最少的分组数量cout << groupCount << endl;return 0;
}

注意:

双指针一般是整数类型的索引,而非指针类型

②使用 n 来初始化 vector 的大小

③将groupCount初始化为0,避免未定义行为

相关文章:

【洛谷贪心算法题】P1094纪念品分组

该题运用贪心算法&#xff0c;核心思想是在每次分组时&#xff0c;尽可能让价格较小和较大的纪念品组合在一起&#xff0c;以达到最少分组的目的。 【算法思路】 输入处理&#xff1a;首先读取纪念品的数量n和价格上限w&#xff0c;然后依次读取每件纪念品的价格&#xff0c;…...

基于coze+微信小程序的ai对话

界面介绍&#xff1a; 代码&#xff1a;&#xff08;替换你的coze的配置&#xff09; <template><view class"container"><!-- 高斯模糊背景 --><view class"animated-bg"><view class"gradient-blob"></view…...

[Linux]项目自动化构建工具-make/Makefile

项目自动化构建工具-make/Makefile make与Makefile单文件Makefile多文件Makefile 缓冲区 首先理清多文件之间的关系&#xff1a; 这里为什么没有包含test.h头文件&#xff1f;因为在当前工作目录下&#xff0c;因此不需要包含test.h&#xff0c;如果把test.h移到上一级目录&…...

Dashboard-frps

通过浏览器查看 frp的状态以及代理统计信息展示。 注&#xff1a;Dashboard 尚未针对大量的 proxy 数据展示做优化&#xff0c;如果出现 Dashboard 访问较慢的情况&#xff0c;请不要启用此功能。 需要在 frps.ini中指定 dashboard服务使用的端口&#xff0c;即可开启此功能&…...

android 新增native binder service 方式(三)

书接上回&#xff0c;继续第三种方式&#xff0c;是手动生成 service binder 的方法,项目结构 1&#xff0c;编译aidl aidl 文件保持不变&#xff0c;如何生成Bn和Bp 文件呢。 aidl -I ./libserviceaidl/aidl -h ./ -o ./ --langcpp libserviceaidl/aidl/com/test/IService.a…...

(IDE接入DeepSeek)简单了解DeepSeek接入辅助开发与本地部署建议

重点&#xff1a;IDE接入DeepSeek是否收费 收费&#xff01; 本文章主要是为了给小白避雷&#xff0c;目前很多文章告诉大家怎么接入DeepSeek&#xff0c;但是并未告知大家是否收费。如果是想白嫖的&#xff0c;就可以不用去接入了。 一、引言 最近爆火的AI人工智能工具DeepSe…...

seasms v9 注入漏洞 + order by注入+​information_schema​解决方法

目录 一、当注入时&#xff0c;information_schema被禁用的解决方法 1.通过sys库可以获取到表名和库名 2.通过无列名注入join获取列名 二、seasms v9 注入漏洞 三、order by注入 一、当注入时&#xff0c;information_schema被禁用的解决方法 information_schema数据库是My…...

【实战 ES】实战 Elasticsearch:快速上手与深度实践-1.3.1单节点安装(Docker与手动部署)

&#x1f449; 点击关注不迷路 &#x1f449; 点击关注不迷路 &#x1f449; 点击关注不迷路 文章大纲 10分钟快速部署Elasticsearch单节点环境1. 系统环境要求1.1 硬件配置推荐1.2 软件依赖 2. Docker部署方案2.1 部署流程2.2 参数说明2.3 性能优化建议 3. 手动部署方案3.1 安…...

如何使用useEffect模拟组件的生命周期?

什么是 useEffect&#xff1f; useEffect 是 React 提供的一个 Hook&#xff0c;用于处理副作用&#xff08;side effects&#xff09;。它允许你在函数组件中执行一些操作&#xff0c;这些操作通常会影响组件的渲染&#xff0c;比如数据获取、订阅、DOM 操作等。通过 useEffe…...

【DeepSeek】私有化本地部署图文(Win+Mac)

目录 一、DeepSeek本地部署【Windows】 1、安装Ollama 2、配置环境变量 3、下载模型 4、使用示例 a、直接访问 b、chatbox网页访问 二、DeepSeek本地部署【Mac】 1、安装Ollama 2、配置环境变量 3、下载模型 4、使用示例 5、删除已下载的模型 三、DeepSeek其他 …...

Python 入门教程(2)搭建环境 | 2.3、VSCode配置Python开发环境

文章目录 一、VSCode配置Python开发环境1、软件安装2、安装Python插件3、配置Python环境4、包管理5、调试程序 前言 Visual Studio Code&#xff08;简称VSCode&#xff09;以其强大的功能和灵活的扩展性&#xff0c;成为了许多开发者的首选。本文将详细介绍如何在VSCode中配置…...

Wireshark详解

Wireshark使用详解 1.Wireshark 简介2.下载与安装1. 下载地址2. 安装步骤&#xff08;以 Windows 为例&#xff09; 3. 界面与核心功能1. 主界面布局2. 常用菜单功能 4. 过滤功能详解1. 过滤类型2. 常用过滤命令 5. 过滤命令与网络结构对应6. 使用注意事项7. 案例分析 TCP 三次…...

《从零开始掌握Python:一份全面的学习指南》

一、为什么选择Python? Python以其简洁优雅的语法和强大的生态系统成为全球最受欢迎的编程语言之一。无论是开发网站、分析数据、构建人工智能模型,还是自动化办公,Python都能轻松胜任。 学习门槛低:代码如英文般直观,例如 print("Hello, World!")。 应用领域广…...

布署elfk-准备工作

建议申请5台机器部署elfk&#xff1a; filebeat(每台app)--> logstash(2台keepalived)--> elasticsearch(3台)--> kibana(部署es上)采集输出 处理转发 分布式存储 展示 ELK中文社区: 搜索客&#xff0c;搜索人自己的社区 官方…...

LlamaFactory-webui:训练大语言模型的入门级教程

LlamaFactory是一个开源框架&#xff0c;支持多种流行的语言模型&#xff0c;及多种微调技术&#xff0c;同时&#xff0c;以友好的交互式界面&#xff0c;简化了大语言模型的学习。 本章内容&#xff0c;从如何拉取&#xff0c;我已经搭建好的Llamafactory镜像开始&#xff0…...

达梦数据库授权给某个用户查询其他指定用户下所有表的权限

方法1&#xff1a; 新版本有一个数据库参数 GRANT_SCHEMA&#xff0c;表示是否开启授予和回收模式权限功能。0&#xff1a;否&#xff1b;1&#xff1a;是 此参数为静态参数&#xff0c;默认是0&#xff0c;将改参数修改为1后&#xff0c;重启数据库生效。 将参数修改为1 S…...

uniapp 微信小程序打包之后vendor.js 主包体积太大,解决办法,“subPackages“:true设置不生效

现在是打包的时候&#xff0c;vendor.js 的内容全部打到了主包里面&#xff0c; 说一下我的方法&#xff1a; 1. 通过发行 小程序打包 这样打包的体积是最小的&#xff0c;打包之后打开微信开发工具&#xff0c;然后再上传 2.manifest.json,在“mp-weixin”里添加代码 "…...

Docker数据卷容器实战

数据卷容器 数据共享 上面讲述的是主机和容器之间共享数据&#xff0c;那么如何实现容器和容器之间的共享数据呢&#xff1f;那就是创建 创建数据卷容器。 命名的容器挂载数据卷&#xff0c;其他容器通过挂载这个&#xff08;父容器&#xff09;实现数据共享&#xff0c;挂载…...

【Eureka 缓存机制】

今天简单介绍一下Eureka server 的缓存机制吧✌️✌️✌️ 一、先来个小剧场&#xff1a;服务发现的"拖延症" 想象你是个外卖小哥&#xff08;客户端&#xff09;&#xff0c;每次接单都要打电话问调度中心&#xff08;Eureka Server&#xff09;&#xff1a;“现在…...

docker-compose方式启动Kafka Sasl加密认证(无zk)

首先参考文档&#xff0c;思考过程可以进行参考https://juejin.cn/post/7294556533932884020#heading-3 用的镜像是Bitnami&#xff0c;对SASL配置进行了简化&#xff0c;需要按照特定格式去配置jass验证 完整配置如下 镜像版本参考&#xff1a;https://hub.docker.com/r/bitn…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...

LOOI机器人的技术实现解析:从手势识别到边缘检测

LOOI机器人作为一款创新的AI硬件产品&#xff0c;通过将智能手机转变为具有情感交互能力的桌面机器人&#xff0c;展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家&#xff0c;我将全面解析LOOI的技术实现架构&#xff0c;特别是其手势识别、物体识别和环境…...

在树莓派上添加音频输入设备的几种方法

在树莓派上添加音频输入设备可以通过以下步骤完成&#xff0c;具体方法取决于设备类型&#xff08;如USB麦克风、3.5mm接口麦克风或HDMI音频输入&#xff09;。以下是详细指南&#xff1a; 1. 连接音频输入设备 USB麦克风/声卡&#xff1a;直接插入树莓派的USB接口。3.5mm麦克…...

绕过 Xcode?使用 Appuploader和主流工具实现 iOS 上架自动化

iOS 应用的发布流程一直是开发链路中最“苹果味”的环节&#xff1a;强依赖 Xcode、必须使用 macOS、各种证书和描述文件配置……对很多跨平台开发者来说&#xff0c;这一套流程并不友好。 特别是当你的项目主要在 Windows 或 Linux 下开发&#xff08;例如 Flutter、React Na…...