洛谷2095题解题报告：贪心+分类计数的优化策略

一、题目解读

洛谷2095题要求处理一组食品数据，每个食品包含脂肪含量和类别。用户需在满足类别消费限制的前提下，选择脂肪含量最高的食品组合，计算总脂肪值。题目核心在于平衡脂肪优先级与类别数量约束，考验对排序和动态规划的应用。

二、解题思路

采用“贪心+分类计数”策略：

1. 定义食品结构体（脂肪含量+类别），按脂肪降序排序，优先处理高脂肪食品。

2. 使用动态数组记录每类食品的最大允许份数及已消费数量。

3. 循环遍历排序后的食品，若当前类别未超限，则计入总脂肪并更新消费计数。

核心逻辑：通过排序确保优先选择高脂肪食品，结合类别限制动态调整，避免超限。

三、解题步骤

1. 输入与初始化：读取n（食品数量）、m（总选择数）、k（类别数），存储每类最大份数。

2. 数据预处理：录入食品数据（脂肪含量+类别），并降序排序。

3. 循环选择：遍历食品，检查类别是否超限，若未超则累加脂肪、更新消费计数。

4. 输出结果：最终总脂肪值。

四、代码与注释

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

struct Food {
    int fat;      // 脂肪含量
    int category; // 食品类别
    bool operator<(const Food &f) const {
        return fat > f.fat; // 按脂肪降序排序
    }
};

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    
    vector<int> max_per_category(k+1); // 每类最大份数
    for(int i = 1; i <= k; ++i) {
        cin >> max_per_category[i];
    }
    
    vector<Food> foods(n);
    for(int i = 0; i < n; ++i) {
        cin >> foods[i].fat >> foods[i].category;
    }
    
    // 按脂肪含量降序排序
    sort(foods.begin(), foods.end());
    
    vector<int> consumed(k+1, 0); // 已消费的各类食品数量
    int total_fat = 0;
    int selected = 0;
    
    for(int i = 0; i < n && selected < m; ++i) {
        int cat = foods[i].category;
        // 检查类别限制
        if(consumed[cat] < max_per_category[cat]) {
            total_fat += foods[i].fat;
            consumed[cat]++;
            selected++;
        }
    }
    
    cout << total_fat << endl;
    return 0;
}

五、总结

本解法通过排序优先+动态约束高效解决题目：

1. 脂肪降序排序确保贪心选择的最优性；

2. 类别计数数组实时监控限制，避免超界；

3. 时间复杂度O(nlogn)（排序）+ O(n)（遍历），空间复杂度O(n+k)。

掌握此类“优先级与条件约束”结合的解题思路，可扩展至多限制场景。

参考：洛谷P2095题解