A18789. 分饼干
填空题
较难
知识点
题目描述
分饼干
题目描述
有n个小朋友，每个小朋友有一个胃口值g[i]；有m块饼干，每块饼干有尺寸s[i]。
一块饼干只能分给一个小朋友，当且仅当饼干尺寸≥小朋友胃口时，小朋友能被满足。
求最多能满足多少个小朋友。
输入格式
第一行两个整数n,m；第二行n个整数表示数组g；第三行m个整数表示数组s。
输出格式
输出一个整数，表示最多满足的小朋友数量。
数据范围: 1≤n,m≤1000
参考答案
#include <iostream>
#include <algorithm>
using namespace std;
int g[1005], s[1005];
int main()
{
int n, m;
cin >> n >> m;
for(int i = 0; i < n; i++) cin >> g[i];
for(int i = 0; i < m; i++) cin >> s[i];
sort(g, g + n); // 小朋友胃口升序
sort(s, s + m); // 饼干尺寸升序
int i = 0, j = 0, ans = 0;
while(i < n && j < m)
{
if(s[j] >= g[i]) // 当前饼干可以满足小朋友
{
ans++;
i++; j++;
}
else j++; // 饼干太小，换下一块
}
cout << ans;
return 0;
}答案解析
1. 贪心规则：用最小能满足当前小朋友的饼干分配，保留大饼干给胃口大的小朋友，避免浪费；
2. 前置操作：将胃口数组、饼干数组全部升序排序；
3. 双指针遍历：饼干够胃口则同时后移、答案+1，否则仅饼干指针后移（饼干太小丢弃）；
4. 算法类型：静态排序贪心，无需堆，时间复杂度O(nlogn+mlogm)。
评分细则
正确输入输出（4分）、双数组排序正确（5分）、双指针逻辑正确（5分）、代码无bug（1分）
上一题
下一题