HIGH91 来硬的

题目描述

共有 枚煤炭和 单位的铁矿石。第 枚煤炭可以融化 单位的铁矿石，燃烧时间为 秒。

你拥有一项魔法，最多可以对一枚煤炭施放，将其升级。若第 枚煤炭被升级，它将可以融化 单位的矿石，而燃烧时间缩短为 秒。

熔炉同一时刻只能燃烧一枚燃料。请求出将所有 单位铁矿石全部烧炼完毕，所需要的最短总时间。

解题思路

这是一个在满足特定“价值”（融化量）要求下，最小化“成本”（燃烧时间）的问题，是典型的背包问题变种。然而，由于单个煤炭的融化量 可能非常大，直接以融化量为维度的DP数组会导致内存溢出。

正确的思路是基于数据范围进行分类讨论和剪枝。任何最优解，要么是仅使用单个煤炭完成任务，要么是使用多个“小”煤炭的组合完成。

1. 策略分类

我们将煤炭分为两类：

  • 大煤炭: 能够单独完成任务的煤炭，即 。
  • 小煤炭: 单独无法完成任务的煤炭，即 。

一个重要的观察是：任何包含“大煤炭”的最优方案，必然只包含那一个“大煤炭”。因为加入任何其他煤炭只会增加时间，而融化量已经足够。

因此，所有可能的解可以被划分为：

  1. 单煤炭方案:
    • 使用一个“大煤炭”（不升级）。
    • 使用一个煤炭（无论大小），将其升级后能够满足 。
  2. 多煤炭方案:
    • 只使用“小煤炭”的组合来完成任务。在这个组合中，我们仍然可以选择对其中一枚“小煤炭”施放魔法。

2. 算法流程

  1. 预处理:

    • 初始化一个全局的最小时间 min_time 为无穷大。
    • 创建一个列表 small_coals 用于存放所有“小煤炭”。
    • 遍历所有 枚煤炭 (x_i, y_i)：
      • 检查单煤炭方案：
        • 如果不升级，若 ，用 更新 min_time。
        • 如果升级，若 ，用 更新 min_time。
      • 如果 ，则将其加入 small_coals 列表。

  2. 对“小煤炭”进行动态规划:

    • 现在的问题是在 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。

  3. 最终答案: 全局 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数组。