GESP 题解库 / 3 级题解 / [GESP202512 三级] 小杨的智慧购物 · 第 2 / 28 题
GESP202512 三级 · B4450 · 入门

智慧购物

有 M 种文具、共 N 件商品,每种只买最便宜的一件,求买齐 M 种的总花费。

📊
N ≤ 10⁵
数据规模
🔢
int
数值类型
⚡
O(N)
时间复杂度
🎯
分组取最小值
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

老师请小杨去文具店购买 M 种不同的文具。商店里共有 N 件文具,每件文具都有一个种类编号(1 到 M)和价格。

小杨的预算有限,他想了一个聪明的办法:对于每种文具,他只买最便宜的那一件(如果同种文具有多件价格相同且都是最便宜的,他只会购买其中的一件)。请你帮小杨计算出,买齐这 M 种文具一共需要花费多少钱。

💡
人话翻译:把 N 件商品按"种类"分组,每组挑出最便宜的那件,然后把 M 件最便宜商品的价格加起来。注意是 M 种都要买到,不是挑 M 件。

🔍 关键词提取

分组统计求最小值数组当桶累加求和

已知条件

项目说明
输入第一行 M、N;随后 N 行每行 K、P(种类编号、价格)
输出买齐 M 种文具的总花费
数据范围1 ≤ M ≤ N ≤ 10⁵
种类编号1 ≤ K ≤ M
价格范围1 ≤ P ≤ 1000
重要保证每个种类至少有一件文具可买

需要解决的问题

02
思维导图
整理解题思路的全貌
🛒 分组取最小再求和
📥 读入与准备
读入 M、N
数组 best[1..M]
全部初始化为 1001
下标即种类编号
🔄 边读边更新
读入一件商品的 K、P
若 P < best[K]
则 best[K] = P
否则忽略这件
➕ 汇总
遍历 best[1..M]
全部累加
输出总价
保证每组非空
⚠️ 注意点
价格是正整数
初始化要足够大
总和 ≤ 1000 × 10⁵
int 够用
03
样例手算推导
样例 M = 2、N = 5 的分组过程

🧮 样例逐步推演

样例数据:2 5,随后 5 行分别是 1 1、1 2、1 1、2 3、2 10。

1
初始化

best[1] = 1001,best[2] = 1001(足够大的哨兵值)

等待更新

2
读入 1 1(种类 1,价格 1)

1 < best[1] = 1001

best[1] 更新为 1

3
读入 1 2(种类 1,价格 2)

2 < best[1] = 1 不成立

忽略,best[1] 仍为 1

4
读入 1 1(种类 1,价格 1)

1 < 1 不成立(相等也不更新)

忽略,best[1] 仍为 1

5
读入 2 3(种类 2,价格 3)

3 < best[2] = 1001

best[2] 更新为 3

6
读入 2 10(种类 2,价格 10)

10 < 3 不成立

忽略,best[2] 仍为 3

7
最后求和

best[1] + best[2] = 1 + 3

✅ 总价 = 4

📊 分组结果一览

种类该种类的所有价格最低价是否买它
11、2、11✅ 买
23、103✅ 买
🔑
关键点:同一件商品只跟"自己种类"的最低价比较,不同种类之间互不影响。所以用数组下标当种类编号是最自然的做法。
04
解法对比
排序法 vs 桶数组法

⚔️ 解法对比

🟢 桶数组(推荐) 推荐

用 best[种类] 记录该种类的最低价,读入时实时更新

  • 时间复杂度 O(N + M)
  • 空间 O(M)
  • 一次遍历,边读边更新
  • 代码最短,约 15 行
💡
为什么它最优:每件商品只看一眼,不需要保存,也不需要排序,是典型的"一遍扫描"解法。

🟠 排序后分组

把所有商品按 (种类, 价格) 排序,每种取第一件

  • 时间复杂度 O(N log N)
  • 空间 O(N) 保存所有商品
  • 需要写比较函数
  • n = 10⁵ 也能过,但没必要
⚠️
注意:排序法要额外的 O(N) 空间存全部商品,而桶数组只用一个长度为 M 的数组。

📈 性能对比

N 的规模桶数组排序法结论
1,000约 1 千次约 1 万次都能过
100,000(本题上限)约 10 万次约 170 万次桶数组明显更省
05
算法流程图
一遍扫描,O(N) 出结果
开始读入 M、Nbest[1..M] 全部初始化为 1001循环 N 次:读入一件商品的 K、PP 比 best[K] 更小吗?是 ✓best[K] = P否 ✗保持原值N 件商品读完了吗?把 best[1..M] 累加求和输出总价结束还有商品没读 → 继续读入
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🛒 分组最低价计算器

第一行输入 M N,之后 N 行每行输入"种类编号 价格"。程序会分组求最低价并汇总。

结果会显示在这里

点按钮开始 →

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

💻 完整 C++ 代码

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

const int MAXP = 1001;              // 价格上限 1000,用 1001 当"无穷大"
int best[100005];

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

    for (int i = 1; i <= M; i++) best[i] = MAXP;   // 初始化为哨兵值

    for (int i = 0; i < N; i++) {
        int k, p;
        scanf("%d %d", &k, &p);
        if (p < best[k]) best[k] = p;             // 只保留每种的最低价
    }

    int total = 0;
    for (int i = 1; i <= M; i++) total += best[i]; // 每种都必须买,直接加
    printf("%d\n", total);
    return 0;
}
🔑
哨兵值的选择:初始化必须比任何合法价格都大。题目保证价格 ≤ 1000,所以用 1001 最省事。养成习惯:初始化值要看数据范围来定,不要凭感觉写 0 或 -1。

📖 关键几行怎么看

代码作用为什么这样写
best[i] = MAXP初始化桶保证第一次遇到任何价格都会更新
if (p < best[k]) best[k] = p;实时更新最低价一遍扫描完成,不用保存所有商品
total += best[i]累加题目保证每种至少一件,所以不会有哨兵值残留
⚠️
如果用贪心"买最便宜的 M 件"会错:那样可能某种买了两件、另一种一件没买。题目要求的是每种各一件。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

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

输入答案考察点
1 1
1 5
5只有一种,只有一件
2 2
1 10
2 20
30每种恰好一件
2 5
1 1
1 2
1 1
2 3
2 10
4题面样例
3 4
3 7
1 2
2 9
3 7
18种类乱序出现,仍要正确分桶
2 3
1 1000
2 1000
1 999
1999价格取到上限 1000
✅
自查清单:① 桶数组是否开到 M + 5 以上?② 初始化值是否大于 1000?③ 求和是从 1 加到 M 吗?

🚨 易错点清单

⚠️
把"买最便宜的 M 件"当答案:题目是"每种各买一件最便宜的",不是"买最便宜的整体 M 件"。
⚠️
初始化写成 0:这样 p < best[k] 永远不成立,最低价永远是 0,答案也就错了。
⚠️
数组开小:种类编号最大是 M(≤ 10⁵),数组要开到 10⁵ + 5,不能按 N 或者按"实际出现过的种类数"来开。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(N + M)
空间复杂度
O(M)
N 最大
10⁵
运算次数
约 10⁵

时间怎么算的?

空间都用在哪?

只用一个长度为 M + 1 的数组记录每种的最低价,不需要保存全部商品,所以空间是 O(M)。

✅ N = 10⁵ 时操作约 10 万次,瞬间完成。

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

🔗 常用技巧小抄

// 桶统计通用套路:下标当"键",数组元素当"值"
int best[100005];                       // 求最小
int cnt[100005];                        // 求次数
long long sum[100005];                  // 求每类的和

for (int i = 1; i <= M; i++) best[i] = 1001;   // 求最小要初始化成"无穷大"
// 求次数则初始化为 0(全局数组默认就是 0)
cnt[k]++;
sum[k] += p;

🌟 举一反三

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

能力点本题怎么用还能迁移到
数组当桶用下标存种类编号计数排序、桶排序、词频统计
哨兵初始化设一个比所有合法值都"极值"的初值求最小值、求最大值、DP 的边界
一遍扫描边读边算,不保存原始数据读入量很大但只需汇总的题目
🌟
思考题:如果把题目改成"每种买最贵的那件",代码要改哪几个地方?(提示:初始化要改成比 0 还小的数,比较符号要反过来。)