问题分析

这是经典的分数背包问题（贪心算法），核心特征是：

1. 物品（物资）可分割，投入部分时间可获得对应比例的价值；
2. 目标是在有限时间 M 内最大化总价值；
3. 最优策略：按单位时间价值（价值/时间）从高到低排序，优先整理单位价值高的物资，直到时间用完。

关键推导：

• 第 i 类物资的单位时间价值 = v_i / t_i；
• 先整理单位价值最高的物资，若时间足够则全部整理，否则整理部分（投入剩余时间，获得对应比例价值）。

完整C++代码实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip> // 用于控制输出小数位数

using namespace std;

// 定义物资结构体：存储整理时间、价值、单位时间价值
struct Material {
    int time;    // 整理总时间t_i
    int value;   // 总价值v_i
    double unit; // 单位时间价值 = value / time
};

// 排序规则：按单位时间价值降序排列
bool compare(const Material& a, const Material& b) {
    return a.unit > b.unit;
}

int main() {
    int N, M;
    cin >> N >> M;
    
    vector<Material> materials(N);
    for (int i = 0; i < N; ++i) {
        cin >> materials[i].time >> materials[i].value;
        // 计算单位时间价值
        materials[i].unit = (double)materials[i].value / materials[i].time;
    }
    
    // 按单位时间价值从高到低排序
    sort(materials.begin(), materials.end(), compare);
    
    double total_value = 0.0; // 总价值
    int remaining_time = M;   // 剩余可用时间
    
    // 贪心选择：优先处理单位价值高的物资
    for (const auto& mat : materials) {
        if (remaining_time <= 0) break; // 时间用完，退出
        
        if (mat.time <= remaining_time) {
            // 时间足够，全部整理
            total_value += mat.value;
            remaining_time -= mat.time;
        } else {
            // 时间不足，整理部分：剩余时间 * 单位价值
            total_value += (double)remaining_time * mat.unit;
            remaining_time = 0; // 时间用完
        }
    }
    
    // 输出结果，保留两位小数
    cout << fixed << setprecision(2) << total_value << endl;
    
    return 0;
}

代码详细解释

1. 数据结构与排序

struct Material {
    int time;
    int value;
    double unit;
};

bool compare(const Material& a, const Material& b) {
    return a.unit > b.unit;
}

• 结构体封装每类物资的核心信息，unit 存储单位时间价值；
• 自定义排序规则，确保物资按单位价值降序排列（优先选性价比高的）。

2. 贪心核心逻辑

for (const auto& mat : materials) {
    if (remaining_time <= 0) break;
    
    if (mat.time <= remaining_time) {
        // 全部整理：累加总价值，扣除时间
        total_value += mat.value;
        remaining_time -= mat.time;
    } else {
        // 部分整理：剩余时间 * 单位价值
        total_value += (double)remaining_time * mat.unit;
        remaining_time = 0;
    }
}

• 遍历排序后的物资，逐个判断是否能完整整理：
  1. 时间足够：直接累加全部价值，剩余时间扣除该物资的整理时间；
  2. 时间不足：计算“剩余时间 × 单位价值”，累加后时间置0（用完）；
• 时间用完后立即退出循环，避免无效遍历。

3. 输出格式控制

cout << fixed << setprecision(2) << total_value << endl;

• fixed：固定小数格式（而非科学计数法）；
• setprecision(2)：强制保留两位小数，符合题目输出要求。

测试用例验证（样例1）

输入：

4 5
1 2  → 单位价值 2/1 = 2.0
2 4  → 单位价值 4/2 = 2.0
3 4  → 单位价值 4/3 ≈ 1.333
2 2  → 单位价值 2/2 = 1.0

排序后顺序：(1,2) → (2,4) → (3,4) → (2,2)

执行过程：

1. 处理 (1,2)：剩余时间 5 ≥ 1 → 总价值=2，剩余时间=4；
2. 处理 (2,4)：剩余时间 4 ≥ 2 → 总价值=6，剩余时间=2；
3. 处理 (3,4)：剩余时间 2 < 3 → 总价值 += 2 × (4/3) ≈ 2.666，总价值=8.666，剩余时间=0；
4. 退出循环，输出保留两位小数 → 8.67（与样例一致）。

边界情况测试

• 时间刚好用完：输入 2 3 + 2 6 + 1 3 → 总价值=6+3=9.00；
• 时间不足整理任何完整物资：输入 2 2 + 3 6 + 4 8 → 单位价值均为2.0，总价值=2×2.0=4.00；
• 单类物资：输入 1 5 + 10 20 → 总价值=5×(20/10)=10.00。

总结

1. 核心算法：分数背包问题的贪心解法，按单位价值降序选择，可分割特性保证贪心策略最优；
2. 关键细节：
   • 排序是贪心的前提，必须按单位价值降序；
   • 处理部分整理时，用“剩余时间 × 单位价值”计算比例价值；
   • 输出需严格保留两位小数，使用 fixed + setprecision(2)；
3. 效率分析：排序时间复杂度 O(N log N)，遍历 O(N)，N≤100 时效率极高，完全满足时间限制。