贪心算法

1.小杨的智慧购物

题目分析

核心问题

需要购买 M 种不同的文具，每种文具只买最便宜的一件，求总花费。

解题思路

这是一个典型的贪心算法问题：

• 贪心策略：对于每种文具，都选择价格最低的那一件
• 局部最优 → 全局最优：每种都选最便宜的，总和自然最小

算法设计

方法：维护最小值数组

1. 数据结构：用数组 mp[i] 记录第 i 种文具的最低价格
2. 初始化：将所有 mp[i] 设为无穷大（或一个很大的数）
3. 遍历更新：读入每件文具，更新对应种类的最低价格
4. 求和输出：将所有种类的最低价格相加

算法流程

输入 M, N
初始化 mp[1...M] = INF

for i = 1 to N:
    输入种类 K, 价格 P
    mp[K] = min(mp[K], P)

总价 = sum(mp[1...M])
输出 总价

代码实现

C++ 实现

#include <iostream>
#include <algorithm>
using namespace std;

const int INF = 1e9;  // 定义无穷大
const int MAXM = 1005; // 最大种类数

int mp[MAXM];  // mp[i] 表示第 i 种文具的最低价格

int main() {
    int M, N;
    cin >> M >> N;
    
    // 初始化：所有种类的最低价格设为无穷大
    for (int i = 1; i <= M; i++) {
        mp[i] = INF;
    }
    
    // 读入 N 件文具，更新最低价格
    for (int i = 1; i <= N; i++) {
        int K, P;
        cin >> K >> P;
        mp[K] = min(mp[K], P);
    }
    
    // 计算总价
    int total = 0;
    for (int i = 1; i <= M; i++) {
        total += mp[i];
    }
    
    cout << total << endl;
    
    return 0;
}

## 样例验证

### 样例 1

**输入**：

2 5
1 1
1 2
1 1
2 3
2 10

**执行过程**：

| 步骤 |  读入   | 更新后 mp[1]  | 更新后 mp[2]  |
| ---- | ------ | ------------ | ------------ |
| 初始 | -      | INF          | INF          |
| 1    | (1,1)  | min(INF,1)=1 | INF          |
| 2    | (1,2)  | min(1,2)=1   | INF          |
| 3    | (1,1)  | min(1,1)=1   | INF          |
| 4    | (2,3)  | 1            | min(INF,3)=3 |
| 5    | (2,10) | 1            | min(3,10)=3  |

**结果**：总价 = 1 + 3 = 4 ✓