孙悟空现在正在天宫偷吃蟠桃,时间有限,王母娘娘一会儿就会回来,孙悟空要在王母娘娘回来之前尽可能多偷吃一点蟠桃。 你的任务是帮助孙悟空决定怎么吃蟠桃才能尽可能多吃。输出孙悟空最多可以吃掉的蟠桃数量。 特别说明:本题中不能直接使用排序库函数,如您使用了排序库函数,即便运行通过也会被判为0分。
第一行两个正整数N和P,N表示蟠桃的数量,P是王母娘娘还有多长时间后会回来。 接下来一行N个整数表示每个蟠桃吃掉所需的时间。 注意,掐着王母娘娘的回来的点吃完是很危险的,所以必须在王母娘娘回来前吃完,不能是回来时刚好吃完。
输出孙悟空最多能吃掉的蟠桃的数量。
8 30 13 4 25 19 17 23 29 8
3
考点:贪心
限制 1 秒 / 256MB | 标准输入输出
参考方向:贪心
每一步都取当前最优,靠问题性质保证局部最优能拼成全局最优。
思路框架(贪心 通法 · 非本题专属)
实现要点:贪心题关键在于排序规则:按什么关键字排序决定了策略是否正确。
复杂度:时间 O(n log n)(含排序) | 空间 O(1) ~ O(n)
该范式的通法易错点
本题在源数据中没有官方考点标签,方向由题面特征推断,仅供参考。
样例 1
8 30 / 13 4 25 19 17 23 29 83解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。
本题来源:美团2023校招笔试-编程题(算法编程题)。