当前位置：首页 > article >正文

【2024华为OD-E卷-100分-木板】（题目+思路+JavaC++Python解析)

article 2025/2/8 10:44:17

题目描述

给定一块木板，其长度为 n 个单位。现在需要在这块木板上切割出 m 个长度为 k 的木板段。每次切割只能沿着木板的整数位置进行，并且每次切割的成本为切割位置到木板两端中较近一端的距离。求最小的切割成本总和。

输入

第一行输入一个整数 n，表示木板的长度。
第二行输入一个整数 m，表示需要切割出的木板段数量。
第三行输入一个整数 k，表示每个木板段的长度。

输出

输出一个整数，表示最小的切割成本总和。

约束条件

1 <= n <= 10^9
1 <= m <= 10^6
1 <= k <= n
m * k <= n

思路分析

贪心算法：
- 我们要尽可能地在靠近木板两端的位置进行切割，这样每次切割的成本会较小。
- 从木板的一端开始，每次尽量靠近当前未切割部分的中间位置进行切割，可以使得剩余部分的两端都能被有效利用。
- 但由于木板长度 n 可能非常大，直接模拟每次切割并不现实。我们需要找到一种更有效的方法来计算总成本。
数学推导：
- 假设木板初始长度为 n，需要切割成 m 段，每段长度为 k。
- 我们可以发现，切割 m-1 次后，木板会被分成 m 段。
- 每次切割的成本可以看作是该切割位置到木板两端中较近一端的距离。
- 我们可以通过数学推导来简化计算，不需要显式地模拟每次切割的位置。
优化：
- 每次切割可以看作是将木板分成两部分，其中一部分被完全利用（长度为 k），另一部分继续切割。
- 我们只需要记录每次切割后剩余木板的长度，并计算该次切割的成本（剩余长度的一半，向下取整）。
- 重复上述过程，直到切割出 m 段木板为止。

Java 编码解析

import java.util.Scanner;

public class WoodBoard {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int k = scanner.nextInt();

        scanner.close();

        long totalCost = 0;
        int remainingSegments = m - 1;
        int currentLength = n;

        while (remainingSegments > 0) {
            // 每次切割的成本是当前长度的一半（向下取整）
            int cutCost = currentLength / 2;
            totalCost += cutCost;

            // 切割后剩余长度为剩余长度减去一个k的长度（因为已经切出一个k长度的木板段）
            currentLength -= k;

            remainingSegments--;
        }

        System.out.println(totalCost);
    }
}

C++ 编码解析

#include <iostream>
using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k;

    long long totalCost = 0;
    int remainingSegments = m - 1;
    int currentLength = n;

    while (remainingSegments > 0) {
        // 每次切割的成本是当前长度的一半（向下取整）
        int cutCost = currentLength / 2;
        totalCost += cutCost;

        // 切割后剩余长度为剩余长度减去一个k的长度（因为已经切出一个k长度的木板段）
        currentLength -= k;

        remainingSegments--;
    }

    cout << totalCost << endl;

    return 0;
}

Python 编码解析

def min_cutting_cost(n, m, k):
    total_cost = 0
    remaining_segments = m - 1
    current_length = n

    while remaining_segments > 0:
        # 每次切割的成本是当前长度的一半（向下取整）
        cut_cost = current_length // 2
        total_cost += cut_cost

        # 切割后剩余长度为剩余长度减去一个k的长度（因为已经切出一个k长度的木板段）
        current_length -= k

        remaining_segments -= 1

    return total_cost

# 输入
n = int(input())
m = int(input())
k = int(input())

# 输出
print(min_cutting_cost(n, m, k))