小欧逛商店

2026/10/24约 1146 字大约 4 分钟

小欧逛商店

OPPO 笔试真题 · 2024 秋招 · 算法岗
判题请到牛客原题提交。

题目描述

小欧准备去商店买东西，商店中有 $n$ 个物品从左向右摆成一排，第 $i$ 个物品的体积为 $a_i$ ，价值为 $b_i$ 。小欧有一个容量为 $x$ 的背包，她每次看到能装进背包里的物品都会装进去，如果装不进去就跳过这个物品。

小欧想知道，她总共能买多少价值的物品？

输入格式

第一行输入两个正整数 $n,x$ ，代表物品数量和背包容量。

接下来的 $n$ 行，每行输入两个正整数 $a_i$ 和 $b_i$ ，代表每个物品的体积和价值。

$1\leq n \leq 10^5$

$1\leq a_i,b_i,x \leq 10^9$

输出格式

一个整数，代表总价值之和。

示例

示例 1

输入：

输出：

说明：

先买第一个物品，价值为 3。

遇到第二个物品时，此时剩余容量为 1，无法购买。

然后买第三个物品，价值为 3。

解题思路

第一步：理解问题本质

题目并不是「从 n 个物品里任意挑选」，而是已经规定好了挑选顺序：
从左往右一个一个看，当前物品装得下就装，装不下就跳过，跳过之后也不会回头。

第二步：为什么这不是 0-1 背包

0-1 背包问的是「容量有限时怎么挑，总价值最大」，挑选顺序可以任意安排，
甚至可以为了后面更值钱的物品而故意放弃当前能装的物品。

这里规则被题意锁死了：能装就必须装，跳过的不能再回头。
所以按性价比排序、动态规划都不适用 —— 它们算出来的是「更优但不是题目所问」的答案。

第三步：一次遍历模拟

维护两个量：

rest：背包剩余容量，初始为 x；
total：已买物品的总价值，初始为 0。

对每个物品 (a_i, b_i)：

若 a_i <= rest，买下它：rest -= a_i，total += b_i；
否则跳过，rest 保持不变。

扫描结束，total 就是答案。比较要用 <= 而不是 <：
体积恰好等于剩余容量时是装得下的。

完整代码实现

import sys


def solve() -> None:
    """按顺序模拟：装得下就装"""
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    rest = int(next(it))          # 剩余容量
    total = 0                     # 已买物品的总价值
    for _ in range(n):
        volume = int(next(it))
        value = int(next(it))
        if volume <= rest:        # 等于剩余容量也算装得下
            rest -= volume
            total += value
    sys.stdout.write(str(total) + "\n")


if __name__ == "__main__":
    solve()

示例推演

输入 n = 3, x = 5，物品依次为 (4, 3)、(2, 5)、(1, 3)：

顺序	体积	价值	处理前 rest	能否装下	处理后 rest	total
1	4	3	5	4 ≤ 5，能	1	3
2	2	5	1	2 > 1，不能	1	3
3	1	3	1	1 ≤ 1，能	0	6

最终输出 6。

第二个物品虽然价值更高（5 > 3），但它来的时候剩余容量只剩 1，只能跳过 ——
这正是「顺序不能改」的含义。

复杂度分析

解法	时间复杂度	空间复杂度	说明
顺序模拟	O(n)	O(1)	边读边处理，不存物品，推荐

易错点总结

1. 把它当成 0-1 背包或按性价比排序

题意规定「看到能装就装」，不允许跳过一个能装的物品去等后面的。
排序或 DP 会算出比题目规则更优的值，样例里那个价值为 5 的物品就是陷阱。

2. 用 `<` 而不是 `<=`

体积恰好等于剩余容量时是装得下的。写成 volume < rest 会漏掉这类物品。

3. 体积和价值读反

每行是先体积 a_i 后价值 b_i。读反了程序也能跑，但结果全错。

4. 数据量到 10^5，用快速读入

sys.stdin.buffer.read().split() 一次读完再迭代，比逐行 input() 更稳。

扩展思考

如果允许任意挑选物品，问题就变成 0-1 背包，需要用动态规划。
如果允许先排序再装，按体积从小到大贪心可以装下最多的件数，
但不一定让总价值最大（价值大的物品可能体积也大）。
如果把「装不下就跳过」改成「装不下就结束购物」，
那就变成求一个最短前缀，只需要在循环里加一句 break。