美团 · 贪心 · 算法编程题
美团 贪心 时限 1 秒 / 256 MB

题目描述

孙悟空现在正在天宫偷吃蟠桃,时间有限,王母娘娘一会儿就会回来,孙悟空要在王母娘娘回来之前尽可能多偷吃一点蟠桃。
你的任务是帮助孙悟空决定怎么吃蟠桃才能尽可能多吃。输出孙悟空最多可以吃掉的蟠桃数量。
特别说明:本题中不能直接使用排序库函数,如您使用了排序库函数,即便运行通过也会被判为0分。

输入输出

输入描述
第一行两个正整数N和P,N表示蟠桃的数量,P是王母娘娘还有多长时间后会回来。
接下来一行N个整数表示每个蟠桃吃掉所需的时间。
注意,掐着王母娘娘的回来的点吃完是很危险的,所以必须在王母娘娘回来前吃完,不能是回来时刚好吃完。
输出描述
输出孙悟空最多能吃掉的蟠桃的数量。

样例共 1 组

样例 1
输入
8 30
13 4 25 19 17 23 29 8
输出
3

算法解析依据一般

考点:贪心

限制 1 秒 / 256MB | 标准输入输出

题目画像

  • 源站时限:1 秒(牛客口径,非本题专属门槛)

解题思路

参考方向:贪心

每一步都取当前最优,靠问题性质保证局部最优能拼成全局最优。

思路框架(贪心 通法 · 非本题专属)

  1. 找出「局部最优怎么选」(往往与排序后的顺序有关)。
  2. 论证(或理性相信)这个贪心策略不会被反例击破:常用交换论证法。
  3. 按策略一次扫描(通常要先排序)得到答案。
  4. 若贪心无法证明,考虑改用 DP(贪心的反例通常来自「当前最优影响后续选择」)。

实现要点:贪心题关键在于排序规则:按什么关键字排序决定了策略是否正确。

复杂度:时间 O(n log n)(含排序) | 空间 O(1) ~ O(n)

该范式的通法易错点

  • 策略不成立却当成贪心做(典型错因)。
  • 排序关键字选错,或相同关键字时的次级规则没考虑。
本题在源数据中没有官方考点标签,方向由题面特征推断,仅供参考。

题目给出的提示

  • 本题中不能直接使用排序库函数,如您使用了排序库函数,即便运行通过也会被判为0分

样例

样例 1

  • 输入:8 30 / 13 4 25 19 17 23 29 8
  • 输出:3

解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。

本题来源:美团2023校招笔试-编程题(算法编程题)。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容:无需作答,直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理,非官方题解