题解 | #来硬的#
来硬的
https://www.nowcoder.com/practice/08dbc77ec79942c1914b002f488b87ee
HIGH91 来硬的
题目描述
共有 枚煤炭和
单位的铁矿石。第
枚煤炭可以融化
单位的铁矿石，燃烧时间为
秒。
你拥有一项魔法，最多可以对一枚煤炭施放，将其升级。若第 枚煤炭被升级，它将可以融化
单位的矿石，而燃烧时间缩短为
秒。
熔炉同一时刻只能燃烧一枚燃料。请求出将所有 单位铁矿石全部烧炼完毕，所需要的最短总时间。
解题思路
这是一个在满足特定“价值”（融化量）要求下，最小化“成本”（燃烧时间）的问题，是典型的背包问题变种。然而，由于单个煤炭的融化量 可能非常大，直接以融化量为维度的DP数组会导致内存溢出。
正确的思路是基于数据范围进行分类讨论和剪枝。任何最优解，要么是仅使用单个煤炭完成任务，要么是使用多个“小”煤炭的组合完成。
1. 策略分类
我们将煤炭分为两类：
- 大煤炭: 能够单独完成任务的煤炭，即
。
- 小煤炭: 单独无法完成任务的煤炭，即
。
一个重要的观察是：任何包含“大煤炭”的最优方案，必然只包含那一个“大煤炭”。因为加入任何其他煤炭只会增加时间，而融化量已经足够。
因此，所有可能的解可以被划分为：
- 单煤炭方案:
- 使用一个“大煤炭”（不升级）。
- 使用一个煤炭（无论大小），将其升级后能够满足
。
- 多煤炭方案:
- 只使用“小煤炭”的组合来完成任务。在这个组合中，我们仍然可以选择对其中一枚“小煤炭”施放魔法。
2. 算法流程
-
预处理:
- 初始化一个全局的最小时间
min_time为无穷大。 - 创建一个列表
small_coals用于存放所有“小煤炭”。 - 遍历所有
枚煤炭
(x_i, y_i)：- 检查单煤炭方案：
- 如果不升级，若
更新
min_time。 - 如果升级，若
更新
min_time。
- 如果不升级，若
- 如果
small_coals列表。
- 检查单煤炭方案：
- 初始化一个全局的最小时间
-
对“小煤炭”进行动态规划:
- 现在的问题是在
small_coals集合中，融化至少矿石的最小时间，其中最多一个可升级。这是一个可以用DP解决的子问题。
- 关于Python I/O: 本题的数据规模（
可达
）意味着输入量可能很大。在Python中，标准的
input()函数在处理大量输入时性能较低，可能导致超时。因此，Python代码实现将采用sys.stdin.readline()以优化读取速度。 - 状态定义:
$dp_0[j]$: 在small_coals中尚未使用魔法，恰好融化单位矿石所需的最短时间。
$dp_1[j]$: 在small_coals中已经使用过一次魔法，恰好融化
- DP容量: 最终融化量可能超过
，DP数组容量设为
足够。
- 状态转移: 遍历
small_coals，用标准的0/1背包（逆序遍历容量）和分层DP的思想更新dp0和dp1数组。 - DP求解: DP完成后，遍历所有
的容量，用
和
的值更新全局
min_time。
- 现在的问题是在
-
最终答案: 全局
min_time即为所求。
代码实现
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 1e9 + 7;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
long long m;
cin >> n >> m;
vector<pair<long long, int>> small_coals;
long long max_small_x = 0;
long long min_time = -1;
for (int i = 0; i < n; ++i) {
long long x;
int y;
cin >> x >> y;
// 检查单煤炭方案
if (x >= m) {
if (min_time == -1 || y < min_time) {
min_time = y;
}
}
if (2 * x >= m) {
if (min_time == -1 || y / 2 < min_time) {
min_time = y / 2;
}
}
// 收集小煤炭
if (x < m) {
small_coals.push_back({x, y});
max_small_x = max(max_small_x, x);
}
}
if (!small_coals.empty()) {
long long capacity = m + 2 * max_small_x;
vector<long long> dp0(capacity + 1, -1);
vector<long long> dp1(capacity + 1, -1);
dp0[0] = 0;
dp1[0] = 0;
for (const auto& coal : small_coals) {
long long x = coal.first;
int y = coal.second;
for (long long j = capacity; j >= 0; --j) {
// 更新 dp1 (已用魔法)
if (j >= x && dp1[j - x] != -1) {
long long new_time = dp1[j - x] + y;
if (dp1[j] == -1 || new_time < dp1[j]) dp1[j] = new_time;
}
if (j >= 2 * x && dp0[j - 2 * x] != -1) {
long long new_time = dp0[j - 2 * x] + y / 2;
if (dp1[j] == -1 || new_time < dp1[j]) dp1[j] = new_time;
}
// 更新 dp0 (未用魔法)
if (j >= x && dp0[j - x] != -1) {
long long new_time = dp0[j - x] + y;
if (dp0[j] == -1 || new_time < dp0[j]) dp0[j] = new_time;
}
}
}
for (long long j = m; j <= capacity; ++j) {
if (dp0[j] != -1) {
if (min_time == -1 || dp0[j] < min_time) min_time = dp0[j];
}
if (dp1[j] != -1) {
if (min_time == -1 || dp1[j] < min_time) min_time = dp1[j];
}
}
}
cout << min_time << endl;
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 x;
int y;
Coal(long x, int y) {
this.x = x;
this.y = y;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long m = sc.nextLong();
List<Coal> smallCoals = new ArrayList<>();
long maxSmallX = 0;
long minTime = -1;
for (int i = 0; i < n; i++) {
long x = sc.nextLong();
int y = sc.nextInt();
if (x >= m) {
if (minTime == -1 || y < minTime) minTime = y;
}
if (2 * x >= m) {
if (minTime == -1 || y / 2 < minTime) minTime = y / 2;
}
if (x < m) {
smallCoals.add(new Coal(x, y));
maxSmallX = Math.max(maxSmallX, x);
}
}
if (!smallCoals.isEmpty()) {
int capacity = (int)(m + 2 * maxSmallX);
long[] dp0 = new long[capacity + 1];
long[] dp1 = new long[capacity + 1];
Arrays.fill(dp0, -1);
Arrays.fill(dp1, -1);
dp0[0] = 0;
dp1[0] = 0;
for (Coal coal : smallCoals) {
long x = coal.x;
int y = coal.y;
for (int j = capacity; j >= 0; j--) {
// Update dp1
if (j >= x && dp1[j - (int)x] != -1) {
long newTime = dp1[j - (int)x] + y;
if (dp1[j] == -1 || newTime < dp1[j]) dp1[j] = newTime;
}
if (j >= 2 * x && dp0[j - (int)(2 * x)] != -1) {
long newTime = dp0[j - (int)(2 * x)] + y / 2;
if (dp1[j] == -1 || newTime < dp1[j]) dp1[j] = newTime;
}
// Update dp0
if (j >= x && dp0[j - (int)x] != -1) {
long newTime = dp0[j - (int)x] + y;
if (dp0[j] == -1 || newTime < dp0[j]) dp0[j] = newTime;
}
}
}
for (int j = (int)m; j <= capacity; j++) {
if (dp0[j] != -1) {
if (minTime == -1 || dp0[j] < minTime) minTime = dp0[j];
}
if (dp1[j] != -1) {
if (minTime == -1 || dp1[j] < minTime) minTime = dp1[j];
}
}
}
System.out.println(minTime);
}
}
import sys
def main():
n, m = map(int, sys.stdin.readline().split())
small_coals = []
max_small_x = 0
min_time = float('inf')
for _ in range(n):
x, y = map(int, sys.stdin.readline().split())
# Check single coal solutions
if x >= m:
min_time = min(min_time, y)
if 2 * x >= m:
min_time = min(min_time, y // 2)
# Collect small coals
if x < m:
small_coals.append((x, y))
max_small_x = max(max_small_x, x)
if small_coals:
capacity = int(m + 2 * max_small_x)
dp0 = [float('inf')] * (capacity + 1)
dp1 = [float('inf')] * (capacity + 1)
dp0[0] = 0
dp1[0] = 0
for x, y in small_coals:
for j in range(capacity, -1, -1):
# Update dp1
if j >= x and dp1[j - x] != float('inf'):
dp1[j] = min(dp1[j], dp1[j - x] + y)
if j >= 2 * x and dp0[j - 2 * x] != float('inf'):
dp1[j] = min(dp1[j], dp0[j - 2 * x] + y // 2)
# Update dp0
if j >= x and dp0[j - x] != float('inf'):
dp0[j] = min(dp0[j], dp0[j - x] + y)
for j in range(int(m), capacity + 1):
min_time = min(min_time, dp0[j], dp1[j])
print(min_time)
if __name__ == "__main__":
main()
算法及复杂度
- 算法: 动态规划 (0/1背包变种) + 分类讨论
- 时间复杂度:
，其中
是“小煤炭”的数量。
用于预处理和分类，
是DP部分的时间复杂度，因为DP的容量上界与
- 空间复杂度:
，需要
的空间存储DP数组。
