贝壳找房 · 模拟 · 算法编程题
贝壳找房 模拟 n ≤ 1e5 时限 1 秒 / 64 MB

题目描述

牛牛是一家商场的经理,为了进一步实现自动化,牛牛希望你能为商场书写一个程序以实现下述功能:
1. 记录仓库中某商品名称、售出一份的收益以及库存数量。
2. 按照顾客下单的顺序自动处理订单,并计算该单是否盈利;若某一订单的需求量大于库存量,则终止处理订单,并给进货处提示警告。
牛牛也知道,程序开发并不是一蹴而就的,但是,他想先看到一个简易化的功能,即:通过文件输入商品情况以及拟定的订单顺序,输出处理完订单后的总盈利或者提示库存不足的警告信息。

输入输出

输入描述
第一行输入两个正整数 n, m( 1≤ m≤ n≤ 10 ^ 5) ,依次代表库存商品种数,以及订单数量。
第 2 到 n+ 1 行,每行输入一个字符串以及两个正整数 s, w, c( s≤ 10; 1≤ w, c≤ 1000) ,依次代表该商品名称,售出一份的收益,以及库存数量。数据保证,这 n 个商品名均不相同。
最后 m 行,按照拟定的订单顺序,一行输入一份待处理的订单,包括一个字符串以及一个整数 t, d( t≤ 10; 1≤ d≤ 1000) ,代表该订单需要的商品名称以及需求数量。
输出描述
如果能够顺利处理所有订单,则一行输出一个整数代表总盈利;否则输出 - x ,其中 x 代表依次处理到第 x 份订单时,库存不足。

样例共 2 组

样例 1 · 根据订单顺序,依次售出十个 apple 和一辆 bike ,总收益 1× 10+ 100= 110 .
输入
3 2
apple 1 10
pear 1 6
bike 100 1
apple 10
bike 1
输出
110
样例 2 · 第二份订单中,需要两辆 bike ,但是商店库存中只有一辆,库存不足。
输入
3 2
apple 1 10
pear 1 6
bike 100 1
apple 10
bike 2
输出
-2

算法解析依据充分

考点:模拟

数据规模 n ≤ 1e5 | 限制 1 秒 / 64MB | 标准输入输出

题目画像

  • 数据规模:m ≤ 1e5,n ≤ 1e5,t ≤ 10
  • 元素值域:w ≤ 1e3,c ≤ 1e3,d ≤ 1e3(注意整数类型选择,避免溢出)
  • 复杂度门槛:只允许 O(n log n) 及更优,朴素 O(n²) 会超时。
  • 源站时限:1 秒(牛客口径,非本题专属门槛)

解题思路

推荐方向:模拟

本题切入点

用哈希表把商品名映射到「单份收益 + 库存」,再按订单顺序模拟扣减;库存不足时立即终止并输出当前订单序号。

不涉及复杂算法,把题目描述的流程原样翻译成代码逐步执行即可。

思路框架(模拟 通法 · 非本题专属)

  1. 用变量记录题目要求的「状态」(当前值、剩余数量、当前位置等)。
  2. 按题面给出的顺序,把每一步操作写成一段代码,逐条执行。
  3. 每一步执行后更新状态,并在题目要求的位置输出或累计答案。
  4. 注意循环的边界:执行多少次、何时终止、是否能终止。

实现要点:结构上通常是一个外层循环包住若干 if/else 分支;只要状态定义清楚,正确率很高。

复杂度:时间 O(操作次数) | 空间 O(状态数)

该范式的通法易错点

  • 终止条件写错导致死循环或漏做最后一次操作。
  • 状态更新顺序颠倒(先改了下标又用旧下标)。
  • 题目里「最多 / 恰好 / 至少」的语义差别没区分。

对照本题

  • 数据规模 n ≤ 1e5,只允许 O(n log n) 及更优,朴素 O(n²) 会超时。
  • 元素值域最大到 1e3 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1:输入 3 2 / apple 1 10 / pear 1 6 / bike 100 1 / apple 10 / bike 1 → 输出 110

根据订单顺序,依次售出十个 apple 和一辆 bike ,总收益 1× 10+ 100= 110 .

样例 2:输入 3 2 / apple 1 10 / pear 1 6 / bike 100 1 / apple 10 / bike 2 → 输出 -2

第二份订单中,需要两辆 bike ,但是商店库存中只有一辆,库存不足。

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

本题来源:【2023】贝壳找房春招Java工程师笔试卷2;【2023】贝壳找房春招C++工程师笔试卷2;【2023】贝壳找房春招前端工程师笔试卷2 等。

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