B4342 [语言月赛 202506] 火车优惠

Maxmilite · 2025-06-18 23:55:23 · 题解

Source & Knowledge

2024 年 6 月语言月赛，由洛谷网校入门计划/基础计划提供。

题目大意

小明想乘火车旅行 x 公里。车票价格如下：

• 前 1 \sim 10 公里，每公里 20 元；
• 超过 10 公里至 50 公里部分，每 5 公里 80 元（不足 5 公里也按 5 公里计算）；
• 超过 50 公里部分，每 10 公里 120 元（不足 10 公里也按 10 公里计算）。

小明可以用一张票或两张票，票的公里数可以随意拆分，目标是总费用最少。求完成 x 公里所需的最小花费。

题目分析

本题的核心在于两个方面：

1. 设计单张票的计费方法；
2. 在所有一张票或两张票的拆分方式中，枚举求出总费用的最小值。

单张票计费方法

我们首先仅考虑一张票，计算长度为 d 公里的单张车票价格：

• 前 10 公里按每公里 20 元计费；
• 若 d > 10，其超出部分最多至 50 公里部分，分为若干个 5 公里段，不足 5 公里部分按 5 公里算，每段收费 80 元；
• 若 d > 50，其超出部分继续按照每 10 公里 120 元计费，若不足 10 公里也按 10 公里计费。

int money = 0;
money += 20 * min(d, 10);
d -= min(d, 10);
int per5km = min(d, 50 - 10) / 5;
if (min(d, 50 - 10) % 5 != 0) {
    per5km++;
}
money += 80 * per5km;
d -= min(d, 50 - 10);
int per10km = d / 10;
if (d % 10 != 0) {
    per10km++;
}
money += 120 * per10km;

枚举所有可能拆分方式

在明确一张票的计算方式后，我们可以自然地枚举 0 \le i \le x，设第一张票走 i 公里，第二张票走 x - i 公里（可为 0 公里）。对于每一组划分，计算 i 公里的费用和 x - i 公里的费用的总和。

在上述的所有总和中取最小值，即为答案，最终输出即可。