按顺序看商品,买得起就买、买不起就跳过,问最终买到几件。
小明有个原则:见到想买的物品,只要能买得起,就一定会买下来,然后才继续往前走;如果买不起就直接跳过。问一天下来小明买了多少件物品。
输入第一行 N,第二行 N 个价格(按见到的先后顺序),第三行初始零花钱 X。
顺序模拟余额递减贪心不可排序
| 项目 | 说明 |
|---|---|
| 输入 | N;N 个价格;初始金额 X |
| 输出 | 买到的物品件数 |
| 数据范围 | 1 ≤ N ≤ 100 |
| 价格范围 | 0 ≤ aᵢ ≤ 100000 |
| 行为规则 | 按顺序,买得起就买(价格 ≤ 当前余额) |
X >= 价格,注意"恰好等于"也表示买得起我们按顺序一件件看,每次判断"当前余额够不够"。
余额 30 ≥ 7 → 买
余额变为 30 − 7 = 23
买了,件数 1
余额 23 ≥ 5 → 买
余额变为 18
买了,件数 2
余额 18 ≥ 9 → 买
余额变为 9
买了,件数 3
余额 9 < 10 → 买不起,跳过
余额保持 9
跳过,件数仍为 3
余额 9 ≥ 7 → 买
余额变为 2
买了,件数 4
余额 2 < 4 → 买不起,跳过
跳过,最终件数 4
| 顺序 | 价格 | 购买前余额 | 判断 | 购买后余额 | 累计件数 |
|---|---|---|---|---|---|
| 1 | 7 | 30 | 30 ≥ 7 ✅ 买 | 23 | 1 |
| 2 | 5 | 23 | 23 ≥ 5 ✅ 买 | 18 | 2 |
| 3 | 9 | 18 | 18 ≥ 9 ✅ 买 | 9 | 3 |
| 4 | 10 | 9 | 9 < 10 ❌ 跳过 | 9 | 3 |
| 5 | 7 | 9 | 9 ≥ 7 ✅ 买 | 2 | 4 |
| 6 | 4 | 2 | 2 < 4 ❌ 跳过 | 2 | 4 |
最终买到 4 件 ✓
按给定顺序遍历,买得起就扣钱计数
把价格排序,从最便宜的开始买
| 方案 | 是否符合题意 | 说明 |
|---|---|---|
| 顺序模拟 | ✅ 正确 | 复现小明的真实行为 |
| 排序贪心 | ❌ 错误 | 改变了题目规定的顺序 |
第一行输入价格列表(空格分隔),第二行输入初始金额,程序会逐件模拟购买过程。
点按钮开始 →
#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],导致后面错误地多买。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
6 | 4 | 题面样例 |
1 | 1 | 余额恰好等于价格,仍然买得起 |
1 | 0 | 差 1 元也买不起 |
3 | 0 | 金额为 0,什么都买不起 |
3 | 3 | 价格为 0 都能买(0 ≥ 0) |
4 | 4 | 买完第 1 件剩 0 元,但后面都是 0 元商品 |
3 | 2 | 买两件花 10,剩 4 不够第三件 |
>=。需要保存价格数组以便按顺序处理;其实也可以边读边判,但必须先读到 X,所以用数组更方便。
✅ N 只有 100,任何写法都瞬间完成;这题考的是读懂"行为规则"而不是想当然地求最优。
// 顺序模拟的通用骨架 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"最优解" | 读题时务必确认问的是哪一种 |
| 余额递减 | 每次操作更新状态 | 背包、预算、资源消耗类题目 |