题解 | #来硬的#

题目链接

题目描述

有 $N$ 枚煤炭和 $M$ 单位的铁矿石。第 $i$ 枚煤炭可以融化 $c_i$ 单位的铁矿石，燃烧时间为 $t_i$ 秒。你拥有一项魔法，至多可以对一枚煤炭施放，将其升级。若第 $i$ 枚煤炭被升级，它的融化量变为 $2 \cdot c_i$ ，燃烧时间变为 $t_i / 2$ 。你需要计算出将所有 $M$ 单位铁矿石烧炼完毕所需的最短时间。

输入:

第一行输入两个整数 $N, M$ ，分别表示煤炭数量与铁矿石总量。( $1 \le N \cdot M \le 10^6$ )
接下来 $N$ 行，每行输入两个整数 $c_i, t_i$ ( $c_i, t_i$ 可达 $10^9$ )。

输出:

输出一个整数，表示烧炼完所有铁矿石所需的最短时间。

解题思路

本题的数据范围 ( $c_i$ 和 $t_i$ 很大, 但 $N \cdot M \le 10^6$ ) 是解题的关键。直接使用常规背包DP会导致内存超限。正确的思路是分情况讨论：

情况A：单个物品解决方案
- 任何一个物品，如果它自身（普通版或升级版）的融化量就能达到 $M$ ，那么它就构成了一个独立的解决方案。我们不需要再组合其他物品，因为那只会增加时间。
- 我们可以在一次遍历中，检查所有物品，找到所有这类“单品即满足”的情况下的最小时间。
情况B：多个“小型”物品组合的解决方案
- 如果最优解是由多个物品组合而成的，那么这些物品的融化量必然都小于 $M$ （否则就退化为情况A）。我们称这些 $c_i < M$ 的物品为“小型”物品。
- 我们可以对所有“小型”物品进行一次背包DP，来求解这种情况下的最优解。
- 状态定义： $dp[j][0]$ 表示融化 $j$ 单位矿石，且尚未使用升级机会时，所需的最短时间。 $dp[j][1]$ 表示已经使用升级机会时的最短时间。
- DP数组大小：我们需要考虑融化量恰好超过 $M$ 的情况。组合中最后加入的物品最大融化量为 $M-1$ ，所以DP数组大小需要开到 $M + (M-1)$ ，即约 $2M$ 。由于 $M \le 10^6$ ，这个大小是可行的。
- 状态转移：对于每个小型物品，逆序遍历融化量 $j$ ，更新 $dp[j][0]$ 和 $dp[j][1]$ 。
最终答案
- 比较从情况A和情况B中找到的两个最优时间，取其较小者即为全局最优解。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const long long INF = -1;

struct Coal {
    long long c, t;
};

void update_min_time(long long &current_min, long long new_time) {
    if (current_min == INF || new_time < current_min) {
        current_min = new_time;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long M;
    cin >> N >> M;

    vector<Coal> all_coals(N);
    for (int i = 0; i < N; ++i) {
        cin >> all_coals[i].c >> all_coals[i].t;
    }

    long long min_total_time = INF;
    vector<Coal> small_coals;
    int max_c_small = 0;

    // 分离小型物品，同时处理单品解决方案
    for (const auto& coal : all_coals) {
        if (coal.c >= M) {
            update_min_time(min_total_time, coal.t);
        }
        if (2 * coal.c >= M) {
            update_min_time(min_total_time, coal.t / 2);
        }
        if (coal.c < M) {
            small_coals.push_back(coal);
            max_c_small = max(max_c_small, (int)coal.c);
        }
    }

    // 处理多件小型物品组合的情况
    if (!small_coals.empty()) {
        int dp_size = M + max_c_small;
        vector<vector<long long>> dp(dp_size + 1, vector<long long>(2, INF));
        dp[0][0] = 0;

        for (const auto& coal : small_coals) {
            for (int j = dp_size; j >= 0; --j) {
                // 普通使用
                if (j >= coal.c) {
                    if (dp[j - coal.c][0] != INF) update_min_time(dp[j][0], dp[j - coal.c][0] + coal.t);
                    if (dp[j - coal.c][1] != INF) update_min_time(dp[j][1], dp[j - coal.c][1] + coal.t);
                }
                // 升级使用
                if (j >= 2 * coal.c) {
                    if (dp[j - 2 * coal.c][0] != INF) update_min_time(dp[j][1], dp[j - 2 * coal.c][0] + coal.t / 2);
                }
            }
        }
        
        for (int j = M; j <= dp_size; ++j) {
            if (dp[j][0] != INF) update_min_time(min_total_time, dp[j][0]);
            if (dp[j][1] != INF) update_min_time(min_total_time, dp[j][1]);
        }
    }

    cout << min_total_time << "\n";
    return 0;
}

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    static class Coal {
        long c, t;
        Coal(long c, long t) {
            this.c = c;
            this.t = t;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        long M = sc.nextLong();

        Coal[] allCoals = new Coal[N];
        for (int i = 0; i < N; i++) {
            allCoals[i] = new Coal(sc.nextLong(), sc.nextLong());
        }

        long minTotalTime = -1;
        List<Coal> smallCoals = new ArrayList<>();
        int maxCSmall = 0;

        for (Coal coal : allCoals) {
            if (coal.c >= M) {
                if(minTotalTime == -1 || coal.t < minTotalTime) minTotalTime = coal.t;
            }
            if (2 * coal.c >= M) {
                if(minTotalTime == -1 || coal.t / 2 < minTotalTime) minTotalTime = coal.t / 2;
            }
            if (coal.c < M) {
                smallCoals.add(coal);
                maxCSmall = Math.max(maxCSmall, (int)coal.c);
            }
        }

        if (!smallCoals.isEmpty()) {
            int dpSize = (int)M + maxCSmall;
            long[][] dp = new long[dpSize + 1][2];
            for (long[] row : dp) Arrays.fill(row, -1);
            dp[0][0] = 0;

            for (Coal coal : smallCoals) {
                for (int j = dpSize; j >= 0; j--) {
                    // Normal use
                    if (j >= coal.c) {
                        if (dp[j - (int)coal.c][0] != -1) {
                            long newVal = dp[j - (int)coal.c][0] + coal.t;
                            if (dp[j][0] == -1 || newVal < dp[j][0]) dp[j][0] = newVal;
                        }
                        if (dp[j - (int)coal.c][1] != -1) {
                            long newVal = dp[j - (int)coal.c][1] + coal.t;
                            if (dp[j][1] == -1 || newVal < dp[j][1]) dp[j][1] = newVal;
                        }
                    }
                    // Upgraded use
                    if (j >= 2 * coal.c) {
                        if (dp[j - (int)(2 * coal.c)][0] != -1) {
                            long newVal = dp[j - (int)(2 * coal.c)][0] + coal.t / 2;
                             if (dp[j][1] == -1 || newVal < dp[j][1]) dp[j][1] = newVal;
                        }
                    }
                }
            }
            
            for (int j = (int)M; j <= dpSize; j++) {
                if (dp[j][0] != -1) {
                    if (minTotalTime == -1 || dp[j][0] < minTotalTime) minTotalTime = dp[j][0];
                }
                if (dp[j][1] != -1) {
                     if (minTotalTime == -1 || dp[j][1] < minTotalTime) minTotalTime = dp[j][1];
                }
            }
        }
        System.out.println(minTotalTime);
    }
}

# 读取输入
N, M = map(int, input().split())
all_coals = []
for _ in range(N):
    all_coals.append(list(map(int, input().split())))

min_total_time = float('inf')
small_coals = []
max_c_small = 0

# 遍历所有煤炭，处理单品解决方案并分离出小型煤炭
for c, t in all_coals:
    # 情况A: 单个普通煤炭满足需求
    if c >= M:
        min_total_time = min(min_total_time, t)
    # 情况A: 单个升级煤炭满足需求
    if 2 * c >= M:
        min_total_time = min(min_total_time, t // 2)
    # 分离出小型煤炭用于后续DP
    if c < M:
        small_coals.append((c,t))
        max_c_small = max(max_c_small, c)

# 情况B: 处理小型煤炭的组合
if small_coals:
    dp_size = M + max_c_small
    # dp[j][0] -> 未使用升级机会, dp[j][1] -> 已使用升级机会
    dp = [[float('inf')] * 2 for _ in range(dp_size + 1)]
    dp[0][0] = 0

    for c, t in small_coals:
        for j in range(dp_size, -1, -1):
            # 作为普通煤炭使用
            if j >= c:
                if dp[j-c][0] != float('inf'):
                    dp[j][0] = min(dp[j][0], dp[j-c][0] + t)
                if dp[j-c][1] != float('inf'):
                    dp[j][1] = min(dp[j][1], dp[j-c][1] + t)
            # 作为升级煤炭使用
            if j >= 2 * c:
                if dp[j-2*c][0] != float('inf'):
                    dp[j][1] = min(dp[j][1], dp[j-2*c][0] + t // 2)

    # 从DP结果中找到满足条件的最短时间
    for j in range(M, dp_size + 1):
        min_total_time = min(min_total_time, dp[j][0], dp[j][1])

print(min_total_time)

算法及复杂度

算法：分类讨论 + 动态规划 (01背包变种)
时间复杂度： $O(N + M \cdot S)$ - 其中 $S$ 是“小型”物品的数量 ( $S \le N$ )。由于 $N \cdot M \le 10^6$ ，且 $S \le N$ ，所以 $M \cdot S \le M \cdot N \le 10^6$ ，总复杂度是可接受的。
空间复杂度： $O(M)$ - 主要开销来自DP数组。