首页 > 其他分享 >455. 分发饼干

455. 分发饼干

时间:2024-09-01 15:24:58浏览次数:12  
标签:分发 begin 饼干 孩子 最小 455 饥饿 end

假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。

对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是满足尽可能多的孩子,并输出这个最大数值。

示例 1:

输入: g = [1,2,3], s = [1,1]
输出: 1
解释: 
你有三个孩子和两块小饼干,3 个孩子的胃口值分别是:1,2,3。
虽然你有两块小饼干,由于他们的尺寸都是 1,你只能让胃口值是 1 的孩子满足。
所以你应该输出 1。

示例 2:

输入: g = [1,2], s = [1,2,3]
输出: 2
解释: 
你有两个孩子和三块小饼干,2 个孩子的胃口值分别是 1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出 2。

题解

因为饥饿度最小的孩子最容易吃饱,所以我们先考虑这个孩子。为了尽量使得剩下的饼干可 以满足饥饿度更大的孩子,所以我们应该把大于等于这个孩子饥饿度的、且大小最小的饼干给这 个孩子。满足了这个孩子之后,我们采取同样的策略,考虑剩下孩子里饥饿度最小的孩子,直到 没有满足条件的饼干存在。 简而言之,这里的贪心策略是,给剩余孩子里最小饥饿度的孩子分配最小的能饱腹的饼干。 至于具体实现,因为我们需要获得大小关系,一个便捷的方法就是把孩子和饼干分别排序。 这样我们就可以从饥饿度最小的孩子和大小最小的饼干出发,计算有多少个对子可以满足条件。

代码

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        auto i=g.begin();
        auto j=s.begin();
        int count=0;
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        while(j!=s.end() && i!=g.end()){
            if(*j<*i){
                j++;
                continue;
            }
            count++;
            i++;
            j++;
        }
        return count;
    }
};

标签:分发,begin,饼干,孩子,最小,455,饥饿,end
From: https://blog.csdn.net/qq_33811080/article/details/141784925

相关文章

  • Qt 事件传递流程-事件处理器|事件分发器|事件过滤器
    (总体传递流程图见文章末尾)自定义控件结构 自定义继承于QLabel的控件类 PropagateLabel.h 自定义窗口 PropagateWidget 在PropagateWidget中添加一个PropagateLabel标签1PropagateWidget::PropagateWidget(QWidget*parent):2QWidget(parent)3{4......
  • 135. 分发糖果(leetcode)
    https://leetcode.cn/problems/candy/description/贪心,策略是确定一侧的正确性,再确定另一侧的正确性,最后综合作为正确答案,其中先确定一侧的正确性是局部最优,确定两侧的正确性的局部最优,且找不到反例就可以推出全局最优答案classSolution{publicintcandy(int[]ra......
  • 代码随想录训练营day29|134.加油站,135. 分发糖果,860.柠檬水找零,406.根据身高重建队列
    加油站想法:暴力遍历?好吧第一遍写的时候读错题意了,以为是比较gas[i]与cost[i+1]的值,shit。intsum1=0,sum2=0;for(intg:gas)sum1+=g;for(intc:cost)sum2+=c;if(sum1<sum2)return-1;//如果gas没cost多intyouliang=0;intn=gas.size()......
  • 银行总分支文件分发系统:在安全与效率之间找到平衡!
    银行的组织结构通常根据其规模、业务范围和地域分布而有所不同,但一般会包括以下几个层级:总行-区域总部或分行-分行-支行-业务中心或服务中心-国际分支机构-附属机构或子公司。  在日常中,存在总分支文件分发的业务场景,文件类型通常包含但不限于以下几种:财务报表:包括资产负债......
  • 深入解析CDN(内容分发网络):架构、优势与实现
    摘要内容分发网络(CDN)是一种通过在多个地理位置部署服务器节点来提高网站加载速度和数据传输效率的网络技术。随着互联网内容的日益丰富和用户对访问速度的高要求,CDN已经成为现代网站和应用不可或缺的一部分。本文将详细介绍CDN的基本概念、工作原理、优势以及如何在Web开发......
  • (路由卷1)-36-路由控制及分发列表
    实验:r1:intlo0ipadd1.1.1.1255.255.255.0ints1/0noshipadd12.1.1.1255.255.255.0routereigrp100noaunet12.0.0.0net1.0.0.0r2:ints1/0noshipadd12.1.1.2255.255.255.0intlo0ipadd2.2.2.2255.255.255.0ints1/1ipadd23.1.1.2255.2......
  • 深入浅出 CDN 链接:从原理到应用,全面解析内容分发网络
    深入浅出CDN链接:从原理到应用,全面解析内容分发网络CDN(ContentDeliveryNetwork,内容分发网络)是近年来互联网发展的重要基石,它通过将内容缓存到全球各地的服务器上,实现内容的快速、高效分发,提升用户体验,降低网站运营成本。本文将从CDN链接的原理、工作机制、应用场景、......
  • 代码随想录day27 || 455 分饼干,376 摆动序列,53 最大子序列和
    分饼干funcfindContentChildren(g[]int,s[]int)int{ //第一思路,双指针暴力解法 varcountint varused2=make([]bool,len(s)) g=quicksort(g) s=quicksort(s) for_,child:=rangeg{ foridx,cookie:=ranges{ if!used2[idx]&&cookie>=......
  • 洛谷 P4556 雨天的尾巴之线段树合并模板
    洛谷P4556题解传送锚点摸鱼环节[Vani有约会]雨天的尾巴/【模板】线段树合并题目背景深绘里一直很讨厌雨天。灼热的天气穿透了前半个夏天,后来一场大雨和随之而来的洪水,浇灭了一切。虽然深绘里家乡的小村落对洪水有着顽固的抵抗力,但也倒了几座老房子,几棵老树被连根拔起,以......
  • 【线段树合并/树上差分】[P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并
    【线段树合并/树上差分】P4556[Vani有约会]雨天的尾巴/【模板】线段树合并思路对\(x,y,lca(u,v),fa_{lca(u,v)}\)四个点进行树上差分,然后用线段树合并动态权值线段树。#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;template<classNode>str......