CSP-X 2018真题 | 快递费用 luogu-B4073

CSP-X 2018真题-快递费用，一道结合分支判断与简单数学运算的入门题目，考察条件语句（或数组映射）和向上取整的处理技巧。适合GESP二级及以上考生练习，难度⭐☆。

B4073 [CSP-X 2018] 快递费用

题目要求

题目描述

某快递公司按邮寄物品的重量收费，收费标准如下：

重量在 $500$ 克以内的，一律 $20$ 元；

超过 $500$ 克的，超重的部分按每 $500$ 克加收费用。超出的重量不足 $500$ 克的，按 $500$ 克计算。例如：$1020$ 克，超重 $520$ 克，需加收两份费用。

根据目的地的不同，加收的费用是不一样的。快递公司划分了五个目的地区域：

• 区域 $1$：每超重 $500$ 克加收 $4$ 元；
• 区域 $2$：每超重 $500$ 克加收 $6$ 元；
• 区域 $3$：每超重 $500$ 克加收 $9$ 元；
• 区域 $4$：每超重 $500$ 克加收 $10$ 元；
• 区域 $5$：每超重 $500$ 克加收 $17$ 元。

给出物品的重量 $w$ 和目的地区域编号 $n$，请你计算快递费用。

输入格式

一行，两个正整数 $w, n$。

输出格式

一行，一个整数，表示快递费用。

输入输出样例 #1

输入 #1

1020 3

输出 #1

38

说明/提示

$1020$ 克的物品寄到区域 $3$，前 $500$ 克收费 $20$ 元；

超重 $1020 - 500 = 520$ 克，还需缴纳 $2$ 份加收的费用；

区域 $3$ 每超重 $500$ 克加收 $9$ 元，共计：$20 + 9 \times 2 = 38$ 元。

数据保证 $1\leq w\leq 10^8$，$1\leq n\leq 5$。

题目分析

本题是一道结合分支判断与数学运算的入门题，考察对分段计费规则的理解和实现。

解题思路分析：

1. 基础费用：

   • 无论物品多重，前 $500$ 克的费用固定为 $20$ 元。
   • 如果 $w \leq 500$，直接输出 $20$ 即可。

2. 超重部分的计算：

   • 超出重量为 $w - 500$ 克，设超出重量为 $a = w - 500$。
   • 超出的部分按每 $500$ 克一份来计费，不足 $500$ 克的按 $500$ 克计算。这实际上就是对超重部分 $a$ 除以 $500$ 后做向上取整。
   • 向上取整的份数公式为：$\lceil \frac{a}{500} \rceil$。

   向上取整技巧详解：

   C++ 中的整数除法（/）是天然向下取整的，即直接截断小数部分。例如 $520 / 500 = 1$（余数 $20$ 被丢弃）。但本题要求"不足 $500$ 克也按 $500$ 克算"，也就是需要向上取整，即 $520 / 500$ 应该得到 $2$。

   向上取整的通用公式为：

   $$\lceil \frac{a}{b} \rceil = \lfloor \frac{a + b - 1}{b} \rfloor$$

   其原理是：在做除法之前，给被除数加上 $b - 1$（即除数减一）。这样做的效果是——

   • 如果 $a$ 能被 $b$ 整除（即没有余数），加上 $b - 1$ 后仍然不会多凑出一个 $b$，向下取整的结果不变。例如：$a = 1000, b = 500$，则 $(1000 + 499) / 500 = 1499 / 500 = 2$，与 $1000 / 500 = 2$ 结果一致。
   • 如果 $a$ 不能被 $b$ 整除（即有余数），原本余数被截断导致少算了一份，但加上 $b - 1$ 后，余数部分被"顶"过了下一个整除点，向下取整的结果恰好多出 $1$，实现了向上取整。例如：$a = 520, b = 500$，原本 $520 / 500 = 1$，但 $(520 + 499) / 500 = 1019 / 500 = 2$，符合预期。

   在本题中，$a = w - 500$，$b = 500$，代入公式得：

   $$\lceil \frac{w - 500}{500} \rceil = \frac{(w - 500) + 499}{500} = \frac{w - 1}{500}$$

   所以在代码中直接写 (w - 1) / 500 即可。虽然化简后的表达式看上去和"超重部分除以500"没有直接联系了，但它确实是由向上取整公式严格推导而来的。

   这是一个在竞赛和日常编程中非常常用的整数运算技巧，建议牢记。

3. 区域费率的映射：

   • 五个区域对应五种不同的加收单价：$4, 6, 9, 10, 17$。
   • 可以使用 if-else 分支逐一判断，但更简洁优雅的做法是使用数组映射：将五个费率存入数组，用区域编号作为下标直接取值。

4. 最终费用：

   • 总费用 $= 20 + \text{超重份数} \times \text{区域单价}$。

5. 数据类型注意：

   • $w$ 最大可达 $10^8$，超重份数最多约为 $2 \times 10^5$，乘以最大单价 $17$ 后约为 $3.4 \times 10^6$，加上基础费用 $20$ 后远小于 int 的上限，因此使用 int 即可安全存储结果。

复杂度分析：

• 时间复杂度：$O(1)$，只需常数次运算。
• 空间复杂度：$O(1)$，只使用几个变量和一个固定大小的数组。

示例代码

#include <iostream>

int main() {
    int w, n;
    std::cin >> w >> n;

    // 五个区域对应的超重加收单价，下标 1~5 对应区域 1~5
    int rate[] = {0, 4, 6, 9, 10, 17};

    // 基础费用 20 元
    int cost = 20;

    // 如果超重，计算超重份数并加收费用
    if (w > 500) {
        // 向上取整：ceil((w-500)/500) = (w-500+499)/500 = (w-1)/500
        int extra = (w - 1) / 500;
        cost += extra * rate[n];
    }

    std::cout << cost << std::endl;
    return 0;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号