【3.1】贪心算法-解分发饼干
一、题目
二、解题思路
贪心算法,亦称贪婪算法,是一种在解决问题时始终选择当前状态下最优解的策略。换言之,该算法并不追求全局最优,而是基于局部最优解的累积效果。
在《算法导论》一书中,对贪心算法有如下阐述:贪心算法在每一步都做出当时认为最佳的选择,即始终采取局部最优的决策,期望这些局部最优选择能够导向全局最优解。
针对本题,贪心算法尤为适用。题目要求尽可能多地满足孩子们的需求,由于饼干不可分割,因此我们可以采取一种策略,即让胃口较大的孩子食用较大的饼干,而胃口较小的孩子则食用较小的饼干。具体操作时,可以从胃口最小的孩子开始,尝试用最小的饼干来满足其需求,若无法满足,则逐步尝试更大的饼干,直至找到合适的饼干或遍历完所有饼干。
#include <iostream>
#include <vector>
#include <algorithm>int findContentChildren(std::vector<int>& g, std::vector<int>& s) {// 先对胃口值和饼干尺寸进行排序std::sort(g.begin(), g.end());std::sort(s.begin(), s.end());int count = 0;for (int j = 0; count < g.size() && j < s.size(); j++) {// 如果当前饼干能满足当前孩子的胃口值,count就加1,否则就继续查找更大的饼干if (g[count] <= s[j])count++;}return count;
}int main() {std::vector<int> g = {1, 2, 3}; // 孩子的胃口值std::vector<int> s = {1, 1}; // 饼干的尺寸int result = findContentChildren(g, s);std::cout << "满足的孩子数量: " << result << std::endl;return 0;
}
三、代码实现
#include <iostream>
#include <vector>
#include <algorithm>int findContentChildren(std::vector<int>& g, std::vector<int>& s) {// 先对胃口值和饼干尺寸进行排序std::sort(g.begin(), g.end());std::sort(s.begin(), s.end());int count = 0;int i = s.size() - 1;for (int j = g.size() - 1; i >= 0 && j >= 0; j--) {// 如果当前饼干能满足当前孩子的胃口值,count就加1,否则就继续查找胃口更小的孩子if (g[j] <= s[i]) {count++;i--;}}return count;
}int main() {std::vector<int> g = {1, 2, 3}; // 孩子的胃口值std::vector<int> s = {1, 1}; // 饼干的尺寸int result = findContentChildren(g, s);std::cout << "满足的孩子数量: " << result << std::endl;return 0;
}
相关文章:
【3.1】贪心算法-解分发饼干
一、题目 假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是, 每个孩子最多只能给一块饼干 。 对每个孩子i,都有一个 胃口值 g[i] ,这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干j,都有一个…...
解决 Error running ‘Application‘: Command line is too long.
一、项目场景: 运行刚拉取下来的项目代码,出现下面问题描述的错误提示。 二、问题描述 Error running Application: Command line is too long. Shorten command line for Application or also for Spring Boot default configuration? 翻译翻译&…...
衡量与归因将是Netflix程序化广告业务的首要任务
作者:刀客doc 8月20日,Netflix宣布今年上半年,品牌的招商收入同比增长了150%,广告主来自旅游、汽车、零售商、快餐和大众快消等行业。这一消息提振了资本市场对Netflix广告业务的信心,8月20日收盘创下每股 698.54 美元…...
关于如何在已有qt项目中添加该项目的单元测试工程
关于如何在已有qt项目中添加该项目的单元测试工程 新建一个子目录工程,把已有项目作为子工程添加进去,然后新建单元测试工程也作为子工程添加进去。单元测试项目要独立于实际项目工程,确保去掉测试项目后,实际项目仍可以正常运行…...
深度剖析数字媒体产业链的无限潜力与创新生态
在当今信息爆炸的时代,数字媒体产业链正以势不可挡的姿态展现出其令人瞩目的无限潜力与创新生态。 数字媒体的发展潜力简直无可限量。从在线视频的爆发式增长,到虚拟现实和增强现实技术带来的沉浸式体验,再到社交媒体平台上丰富多彩的内容创…...
集团数字化转型方案(十二)
集团数字化转型方案致力于通过构建一个集成化的数字平台,全面应用大数据分析、人工智能、云计算和物联网等前沿技术,推动业务流程、管理模式和决策机制的全面升级。该方案将从业务流程的数字化改造开始,优化资源配置,提升运营效率…...
Andrid异步更新UI:Handler(二)深入了解:Message你真的会创建?它是如何子线程和主线程通知?
目录 为什么会有HandlerHandler的原理,以及对象讲解主线程的loop在哪里,为什么主线程loop没有阻塞呢?Looper如何保证唯一Handler为什么会引发内存泄漏呢?Message应该如何创建它? 一、为什么会有Handler 线程分为主线…...
2025计算机毕设50条小众好做的Java题目【计算机毕设选题推荐】
随着2025年的到来,计算机专业的学生们又迎来了毕业设计的关键时刻。对于大多数学生来说,选择一个合适的毕业设计题目往往是一项艰巨的任务。本文旨在为那些正在为毕业设计题目烦恼的同学们提供一些灵感和建议,特别是针对使用Java技术栈的同学…...
day06_算法训练
一. Stream流 1.1 Stream流概述 概念: jdk1.8以后提供的新的API, 主要用于批量操作数据(集合的另外一种操作方式),代码非常简洁 流式处理思想: 2.2 Stream对象获取 1.单列集合的Stream流对象获取 2.双列集合的Stream流对象获取 3.数组的Stream流对象获取 4.散装数据的St…...
@SpringBootTest单元测试中报错:无法自动装配,找不到 ‘XXX‘ 类型的 Bean
一开始照着网上教程讲Springboot原理中的代码来copy写的↓ import com.google.gson.Gson; import com.itheima.pojo.Result; import org.junit.jupiter.api.Test; import org.springframework.beans.factory.annotation.Autowired; import org.springframework.boot.test.cont…...
nodemon学习(一)简介、安装、配置、使用
nodemon用来监视node.js应用程序中的任何更改并自动重启服务,非常适合用在开发环境中。以前,我们开发一个node后端服务时,每次更改文件,均需重启一下,服务才能生效。这使我们的开发效率降低了很多。nodemon的出现,可以…...
【Qt从摄像头视频中获取数据】
有时候需要在视频上画图,所以需要能获取到每一帧视频数据。 以前从视频文件或视频流中得到帧,一般都是使用qt ffmpeg或qt vlc。 qt对显示处理视频大体有以下方法: QMediaPlayer QVideoWidget 这种方法只适合简单的显示视频功能ÿ…...
视频截取中的UI小组件
引言 视频截取在社交类 APP 中十分常见。有了上传视频的功能,就不可避免地需要提供截取和编辑的选项。如果我们过度依赖第三方库,项目的代码可能会变得异常臃肿,因为这些库往往包含许多我们用不到的功能,而且它们的 UI 样式和功能…...
java设计模式--结构型模式
结构性模式:适配器模式、桥接模式、装饰模式、组合模式、外观模式、享元模式、代理模式 适配器模式 适配器模式(Adapter Pattern) 充当两个不兼容接口之间的桥梁,属于结构型设计模式。目的是将一个类的接口转换为另一个接口&am…...
消息中间件:Kafka消息丢失与堆积问题分析与解决方案
消息中间件:Kafka消息丢失与堆积问题分析与解决方案 Kafka作为分布式消息系统,广泛应用于实时数据流处理、大数据分析等领域。然而,在实际应用中,Kafka可能会面临消息丢失和消息堆积的问题,这些问题如果得不到有效处理…...
mac终端代理配置指南
终端代理配置指南 在 macOS 中,你可以通过几种不同的方法来配置终端代理。这里介绍两种常见的设置方式:使用 alias 和 shell 函数。 方法 1:使用 Alias 配置代理 打开终端配置文件 默认情况下,macOS 终端使用的是 zsh。如果你的系…...
mbedTLS生成客户端,服务端密钥及CA证书
1. mbedTLS源码:https://github.com/Mbed-TLS/mbedtls.git 2. 生成步骤: 2.1 编译上述源码 2.2 生成CA私钥和自签名证书: 进入编译的build目录,比如:/mbedtls-development/build# 2.2.1生成CA私钥 执行下面的命令&…...
如何有效应对突发技术故障:以网易云音乐为例
引言 在互联网行业,任何一个在线服务都可能遭遇突发的技术故障。这些故障不仅影响用户体验,还可能对公司的品牌形象造成损害。因此,如何快速响应并高效解决这些问题成为了每一个开发团队的重要课题。本文将以网易云音乐在2024年8月19日下午遭…...
上传文件到github仓库
REF: https://blog.csdn.net/litianxiang_kaola/article/details/74075151 已有repository,往仓库里更新内容 点击gitlab里的clone 在git bash中使用git clone,这个时候会将网上的仓库下载到本地,你可以把想要更新的内容直接拖到仓库里 …...
clip-path实现图片边角的裁剪
img {clip-path: polygon(0 7px,7px 0,calc(100% - 20px) 0,100% 20px,100% 100%,16px 100%,0 calc(100% - 16px));}每一个逗号隔开的就是路径坐标 左上角的两个点 0 7px ,7px 0 右上角 calc(100% - 20px) 0,100% 20px 相当于通过这些点练成的线的圈起来的部分就是剩…...
(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...
可靠性+灵活性:电力载波技术在楼宇自控中的核心价值
可靠性灵活性:电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中,电力载波技术(PLC)凭借其独特的优势,正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据,无需额外布…...
el-switch文字内置
el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...
高等数学(下)题型笔记(八)空间解析几何与向量代数
目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍
文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...
Mac下Android Studio扫描根目录卡死问题记录
环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...
