题解

题意分析

题目要求将一定量的葡萄酒装瓶，每个酒瓶有最小和最大容量限制：

• 输入葡萄酒总量（升）和酒瓶规格数量
• 每种酒瓶规格给出最小和最大容量（毫升）
• 目标是用尽可能多的酒瓶装酒，使每个酒瓶的装量都在其容量范围内
• 输出无法装瓶的剩余酒量

解题思路

1. 贪心算法：优先使用容量大的酒瓶，可以更有效地减少剩余酒量
2. 单位转换：将葡萄酒总量从升转换为毫升
3. 排序处理：将酒瓶按最大容量从大到小排序
4. 装瓶计算：
   • 计算每种酒瓶最多能装多少瓶
   • 确保装瓶后剩余酒量不为负
   • 更新剩余酒量

实现步骤

1. 输入处理：读取葡萄酒总量和酒瓶规格
2. 单位转换：将葡萄酒量从升转换为毫升
3. 规格排序：按酒瓶最大容量降序排列
4. 贪心装瓶：
   • 遍历每种酒瓶规格
   • 计算该规格酒瓶能装的最大数量
   • 调整数量确保不超剩余酒量
   • 更新剩余酒量
5. 输出结果：输出无法装瓶的剩余酒量

代码注释

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

// 定义酒瓶结构体，存储最小和最大容量
struct Bottle {
    int min_cap;
    int max_cap;
};

int main() {
    int wine_liters, bottle_types;
    cin >> wine_liters >> bottle_types; // 读取葡萄酒总量(升)和酒瓶规格数量
    
    // 将葡萄酒总量转换为毫升(1升=1000毫升)
    int wine_ml = wine_liters * 1000;
    
    // 读取每种酒瓶的最小和最大容量
    vector<Bottle> bottles(bottle_types);
    for (int i = 0; i < bottle_types; ++i) {
        cin >> bottles[i].min_cap >> bottles[i].max_cap;
    }
    
    // 将酒瓶按最大容量从大到小排序(贪心策略)
    sort(bottles.begin(), bottles.end(), [](const Bottle& a, const Bottle& b) {
        return a.max_cap > b.max_cap;
    });
    
    int remaining = wine_ml; // 初始化剩余酒量
    
    // 遍历每种酒瓶规格
    for (const auto& bottle : bottles) {
        if (remaining <= 0) break; // 如果酒已装完则终止
        
        // 计算使用当前规格酒瓶的最大可能数量
        int max_bottles = remaining / bottle.min_cap;
        
        // 如果能装至少1瓶
        if (max_bottles >= 1) {
            int used_bottles = max_bottles; // 初始使用最大数量
            
            // 计算使用这些瓶子后的剩余酒量
            int new_remaining = remaining - used_bottles * bottle.max_cap;
            
            // 如果剩余酒量为负，需要调整瓶子数量
            if (new_remaining < 0) {
                // 计算需要减少的瓶子数量
                int reduction = (-new_remaining + bottle.max_cap - bottle.min_cap) / 
                               (bottle.max_cap - bottle.min_cap);
                used_bottles -= reduction;
                if (used_bottles < 0) used_bottles = 0; // 确保不为负
            }
            
            // 更新剩余酒量
            remaining -= used_bottles * bottle.max_cap;
        }
    }
    
    cout << remaining << endl; // 输出无法装瓶的剩余酒量
    
    return 0;
}

复杂度分析

• 时间复杂度：主要由排序决定，为$O(n \log n)$，其中$n$为酒瓶规格数量
• 空间复杂度：$O(n)$，用于存储酒瓶规格信息