GESP 题解库 / 3 级题解 / [GESP样题 三级] 逛商场 · 第 25 / 28 题
GESP样题 三级 · B3848 · 入门

逛商场

按顺序看商品,买得起就买、买不起就跳过,问最终买到几件。

📊
N ≤ 100
商品数量
🔢
价格 ≤ 10⁵
价格范围
⚡
O(N)
时间复杂度
🎯
顺序贪心模拟
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

小明有个原则:见到想买的物品,只要能买得起,就一定会买下来,然后才继续往前走;如果买不起就直接跳过。问一天下来小明买了多少件物品。

输入第一行 N,第二行 N 个价格(按见到的先后顺序),第三行初始零花钱 X。

💡
人话翻译:这是个"边走边买"的模拟题。关键点:必须按给定顺序处理,不能先排序再挑便宜的买——那样买到的件数可能更多,但不符合小明的行为规则。

🔍 关键词提取

顺序模拟余额递减贪心不可排序

已知条件

项目说明
输入N;N 个价格;初始金额 X
输出买到的物品件数
数据范围1 ≤ N ≤ 100
价格范围0 ≤ aᵢ ≤ 100000
行为规则按顺序,买得起就买(价格 ≤ 当前余额)

需要解决的问题

02
思维导图
整理解题思路的全貌
🛍️ 按顺序边走边买
📥 读入
N 件商品
价格按见到顺序给出
初始金额 X
数组保存价格
🔁 顺序模拟
i 从 0 到 N−1
若 X ≥ 价格 → 买
余额减去价格,件数加 1
否则跳过继续
📤 输出
输出买到的件数
不需要输出余额
不需要输出买了哪些
只数个数
⚠️ 易错点
错误地排序后贪心
把"买得起"写成"严格大于"
余额没更新
顺序被打乱
03
样例手算推导
样例 6 件商品逐步模拟

🧮 样例:价格 7 5 9 10 7 4,初始 30 元

我们按顺序一件件看,每次判断"当前余额够不够"。

1
第 1 件,价格 7

余额 30 ≥ 7 → 买

余额变为 30 − 7 = 23

买了,件数 1

2
第 2 件,价格 5

余额 23 ≥ 5 → 买

余额变为 18

买了,件数 2

3
第 3 件,价格 9

余额 18 ≥ 9 → 买

余额变为 9

买了,件数 3

4
第 4 件,价格 10

余额 9 < 10 → 买不起,跳过

余额保持 9

跳过,件数仍为 3

5
第 5 件,价格 7

余额 9 ≥ 7 → 买

余额变为 2

买了,件数 4

6
第 6 件,价格 4

余额 2 < 4 → 买不起,跳过

跳过,最终件数 4

顺序价格购买前余额判断购买后余额累计件数
173030 ≥ 7 ✅ 买231
252323 ≥ 5 ✅ 买182
391818 ≥ 9 ✅ 买93
41099 < 10 ❌ 跳过93
5799 ≥ 7 ✅ 买24
6422 < 4 ❌ 跳过24

最终买到 4 件 ✓

🔑
如果排序后会怎样?把价格排序成 4、5、7、7、9、10,30 元能买到 4 + 5 + 7 + 7 = 23(4 件),再加 9 就是 32 > 30,还是 4 件。但这不是重点——重点是题目规定了"按顺序",所以必须按顺序模拟。
04
解法对比
顺序模拟 vs 排序后贪心

⚔️ 解法对比

🟢 顺序模拟(唯一正确解) 推荐

按给定顺序遍历,买得起就扣钱计数

  • 时间 O(N)
  • 空间 O(N) 存价格
  • 完全符合题意的行为规则
  • 代码 10 行
💡
为什么这是唯一正确解:题目描述的是小明的具体行为("按顺序看到、买得起就买"),不是"最多能买几件"。

🔴 排序后贪心

把价格排序,从最便宜的开始买

  • 在本题是错误的
  • 它求的是"最多能买几件"
  • 与小明的实际行为不符
  • 顺序信息被破坏
⚠️
重要区别:"最多能买几件"和"小明实际买了几件"是两个不同的问题。本题问的是后者,所以不能排序。

📈 性能对比

方案是否符合题意说明
顺序模拟✅ 正确复现小明的真实行为
排序贪心❌ 错误改变了题目规定的顺序
05
算法流程图
一遍扫描,边买边扣钱
开始读入 N、价格数组 a、初始金额 Xi 从 0 到 N − 1X ≥ a[i] 吗?是 ✓X 减去 a[i],件数加 1否 ✗跳过这件所有商品都看完了吗?输出买到的件数结束还有商品 → 继续看
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🛍️ 逛商场模拟器

第一行输入价格列表(空格分隔),第二行输入初始金额,程序会逐件模拟购买过程。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

int a[105];

int main() {
    int N;
    scanf("%d", &N);

    for (int i = 0; i < N; i++) scanf("%d", &a[i]);

    int X;
    scanf("%d", &X);

    int cnt = 0;
    for (int i = 0; i < N; i++) {     // 必须按给定顺序
        if (X >= a[i]) {              // 买得起(包含恰好等于)
            X -= a[i];                // 扣钱
            cnt++;                    // 计数
        }
        // 买不起就什么都不做,继续看下一件
    }

    printf("%d\n", cnt);
    return 0;
}
🔑
为什么用 >= 而不是 >?"能买得起"意味着价格不超过余额。如果余额恰好等于价格,也买得起(买完剩 0 元)。写成 > 会漏掉这种情况。

📖 关键几行怎么看

代码作用为什么这样写
for (int i = 0; i < N; i++)按顺序遍历顺序是题目规则的一部分,不能改
X >= a[i]判断买得起等于也买得起
X -= a[i]; cnt++;扣钱并计数两件事都要做,缺一不可
int X余额类型初始金额不大,int 足够
⚠️
三个坑:① 排序后从便宜的开始买(改变了题目规定的行为顺序);② 判断写成 X > a[i],余额恰好等于价格时误判为买不起;③ 忘记扣钱 X -= a[i],导致后面错误地多买。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
6
7 5 9 10 7 4
30
4题面样例
1
5
5
1余额恰好等于价格,仍然买得起
1
6
5
0差 1 元也买不起
3
1 2 3
0
0金额为 0,什么都买不起
3
0 0 0
0
3价格为 0 都能买(0 ≥ 0)
4
10 1 1 1
10
4买完第 1 件剩 0 元,但后面都是 0 元商品
3
5 5 5
14
2买两件花 10,剩 4 不够第三件
✅
自查清单:① 是按顺序遍历的吗?② 判断用了 ≥ 吗?③ 买了之后扣钱了吗?

🚨 易错点清单

⚠️
排序后贪心:虽然可能买到更多,但不符合题目描述的"按顺序"行为,本题必须顺序模拟。
⚠️
判断写成严格大于:余额恰好等于价格时应判定为"买得起",所以要用 >=。
⚠️
忘记扣钱:只计数不扣钱,会把后面买不起的也误判为买得起。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(N)
空间复杂度
O(N)
N 最大
100
运算量
100 次

时间怎么算的?

空间都用在哪?

需要保存价格数组以便按顺序处理;其实也可以边读边判,但必须先读到 X,所以用数组更方便。

✅ N 只有 100,任何写法都瞬间完成;这题考的是读懂"行为规则"而不是想当然地求最优。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 顺序模拟的通用骨架
int budget = X, cnt = 0;
for (int i = 0; i < N; i++) {
    if (budget >= cost[i]) {      // 满足条件就执行
        budget -= cost[i];
        cnt++;
    }
    // 不满足就跳过,什么都不做
}

// 对比:如果题目问的是"最多能买几件"
// 那就应该先排序再贪心
sort(cost, cost + N);
int best = 0, rest = X;
for (int i = 0; i < N; i++) {
    if (rest >= cost[i]) { rest -= cost[i]; best++; }
}

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
顺序模拟按给定顺序判断执行所有"过程/行为"类模拟题
区分问题类型"实际行为"vs"最优解"读题时务必确认问的是哪一种
余额递减每次操作更新状态背包、预算、资源消耗类题目
🌟
思考题:题目改成"求小明最多能买多少件"(允许调整顺序),答案会变成几件?(提示:把价格排序:4、5、7、7、9、10,30 元依次买 4、5、7、7 共 23,再加 9 就 32 超了,所以最多还是 4 件——但这只是巧合,很多数据下两种答案会不同。)