小杨的智慧购物 题解

题目分析

本题要求我们从给定的 $N$ 件文具中，为 $M$ 种不同的文具各自挑选价格最低的一件，并计算这些最低价格的总和。题目保证每个种类的文具至少出现一次，因此一定能买齐所有种类。数据范围中 $M, N \leq 10^5$，价格 $P_i \leq 10^3$，所以直接遍历所有文具并记录每种的最低价是一种简单且高效的做法。

解题思路

我们可以把问题拆解为两个步骤：

1. 遍历所有文具，记录每种文具的最低价格
   使用一个数组 min_price[k] 表示第 $k$ 种文具当前找到的最低价格。初始时，由于价格都是正整数，可以将 min_price 的所有元素设为一个很大的数（例如 $10^9$）。然后依次读取每件文具的种类 K 和价格 P，用 min(min_price[K], P) 来更新该种类的最低价格。

2. 求和输出
   遍历 $1$ 到 $M$ 的每一个种类，将 min_price[k] 累加到总价 total_cost 中，最后输出 total_cost。

由于 $M$ 和 $N$ 都可能达到 $10^5$，我们应当使用时间复杂度为 $O(N + M)$ 的算法，上面的两次遍历正好满足要求。数组大小开 $100005$ 足够容纳所有种类编号。

算法说明

1. 读入 $M$ 和 $N$。
2. 初始化长度为 $M+1$ 的数组 min_price，每个元素赋值为一个大于 $1000$ 的整数（因为单件文具价格最高为 $1000$），如 $10^9$。
3. 循环 $N$ 次，每次读入种类 $K$ 和价格 $P$，执行 min_price[K] = min(min_price[K], P)。
4. 设 total_cost = 0，循环 $k$ 从 $1$ 到 $M$，累加 min_price[k]。
5. 输出 total_cost。

时间复杂度分析

• 初始化数组：$O(M)$
• 遍历 $N$ 件文具更新最低价：$O(N)$
• 累加总和：$O(M)$
  总体时间复杂度为 $O(N + M)$，在 $N, M \leq 10^5$ 时可以在 1 秒内轻松完成。
• 空间复杂度：需要一个大小为 $M$ 的数组，即 $O(M)$，满足内存限制。

参考代码

下面是基于上述思路的 C++ 实现，代码中已加入详细注释：

cpp
复制
1#include <iostream>
2#include <algorithm>  // 提供 min 函数（部分编译器可从 iostream 间接获得，但显式包含更规范）
3using namespace std;
4
5int min_price[100005];  // 保存每种文具的最低价，下标从 1 开始
6
7int main() {
8    int M, N;
9    cin >> M >> N;
10
11    // 初始化为一个很大的值，比所有可能的价格都大
12    for (int i = 1; i <= M; ++i) {
13        min_price[i] = 1000000000;
14    }
15
16    // 读入所有文具，更新对应种类的最低价
17    for (int i = 0; i < N; ++i) {
18        int K, P;
19        cin >> K >> P;
20        if (P < min_price[K]) {
21            min_price[K] = P;  // 等价于 min_price[K] = min(min_price[K], P);
22        }
23    }
24
25    // 计算总花费
26    int total_cost = 0;
27    for (int k = 1; k <= M; ++k) {
28        total_cost += min_price[k];
29    }
30
31    cout << total_cost << endl;
32    return 0;
33}

代码解释

• 数组 min_price：声明为全局数组，大小开到 $100005$，能够容纳 $M$ 最大为 $10^5$ 的情况。下标从 $1$ 到 $M$ 对应文具的种类编号。
• 初始化：将每个元素赋值为 $10^9$，因为实际价格最大只有 $1000$，这样后续的比较一定会被实际价格更新。
• 更新最低价：读取每件文具，若当前价格小于已记录的最低价，则进行更新。可以用 min 函数或 if 判断，效果相同。
• 累加与输出：最后用一个循环将每种文具的最低价相加，输出总和。

注意：原参考代码中 #include <cstring> 是多余的，此处已修正。另外，初始化数组时从下标 0 开始也无妨，但为避免混淆，本例中明确从 1 开始处理种类编号。

总结

本题考察了对数组的简单应用以及如何在一组数据中筛选最值。关键在于正确初始化一个足够大的“最小值”数组，然后遍历更新。由于数据范围适中，$O(N)$ 的遍历效率完全满足要求。这种“每类取最小”的思想在后续的贪心题目中也会经常遇到，希望同学们能够熟练掌握。