当前位置: 首页 > 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…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...