当前位置:首页 > 题解目录 > 正文内容

【题解】分发饼干

亿万年的星光4周前 (01-15)题解目录106

【题目描述】

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

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

【输入描述】

3行,第一行n和m表示有n个孩子的胃口,m表示有块饼干。

第二行是这n个孩子的胃口,每个数中间用空格隔开

第三行是m块饼干的尺寸。

【输出描述】

满足尽可能多的最大数值

【样例1输入】

3 2
1 2 3
1 1

【样例1输出】

1

【样例1解释】

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

【样例2输入】

2 3
1 2
1 2 3

【样例2输出】

2

【样例2解释】

你有两个孩子和三块小饼干,2 个孩子的胃口值分别是 1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出 2。

【数据范围】

  • 1 <= g.length <= 3 * 104

  • 0 <= s.length <= 3 * 104

  • 1 <= g[i], s[j] <= 231 - 1

【思路】

    胃口值 g最小的孩子最容易吃饱,所以我们先考虑最容易吃饱的孩子。为了尽量使得剩下的饼干可以满足饥饿度更大的孩子,所以我们应该把大于等于这个孩子饥饿度的、且大小最小的饼干给这个孩子。我们只需要将孩子按照胃口值从小到大排列,将饼干按照尺寸从小到大排列,每次找到胃口值最小的孩子,并将最小的能两足这个孩子的饼干分配给他即可。


【参考答案】

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    int g[1000], s[1000]; // 假设最多有1000个孩子和1000块饼干

    // 输入孩子的胃口值
    for (int i = 0; i < n; i++) {
        cin >> g[i];
    }

    // 输入饼干的尺寸
    for (int j = 0; j < m; j++) {
        cin >> s[j];
    }

    // 对孩子的胃口值和饼干的尺寸进行排序
    sort(g, g + n);
    sort(s, s + m);

    int i = 0, j = 0, count = 0;

    // 贪心算法:尽可能满足胃口最小的孩子
    while (i < n && j < m) {
        if (s[j] >= g[i]) {
            count++;
            i++;
            j++;
        } else {
            j++;
        }
    }

    cout << count << endl;

    return 0;
}


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

【题解】相关数

【题目描述】一个数与另一个数如果含有相同数字和个数的字符,则称两数相关。现有一堆乱七八糟的整数,里面可能充满了彼此相关的数,请你用一下手段,自动地将其剔除。【输入描述】每组数据前有一个N(<10...

【题解】连通块

【题目描述】一个n × m的方格图,一些格子被涂成了黑色,在方格图中被标为1,白色格子标为0。问有多少个四连通的黑色格子连通块。四连通的黑色格子连通块指的是一片由黑色格子组成的区域,其中的每个黑色格子...

求Π的值

【题目描述】根据公式:arctanx(x)=x−x^3/3+x^5/5−x^7/7+…和π=6arctanx(1/√3).定义函数arctanx(x),求当最后一项小于10^(−6)时π的值。【输入描...

【题解】结构体与闰年

【题目描述】定义一个结构体变量(包括年、月、日)。计算该日在本年中是第几天,注意闰年问题。【输入描述】年月日【输出描述】当年第几天【样例输入】2000 12 31【样例输出】366...

【题解】最小子序列

【题目描述】给你一个数组 nums,请你从中抽取一个子序列,满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。如果存在多个解决方案,只需返回 长...

亲和数

【题目描述】自然数a的因子是指能整除a的所有自然数,但不含a本身。例如12的因子为:1,2,3,4,6。若自然数a的因子之和为b,而且b的因子之和又等于a,则称a,b为一对“亲和数” 。求最小的一对亲...