(六) 从计数要求推导向上取整
1. 完整示例:载客人数与最少车辆数
题目原文(自拟): 有 people 个人,每辆车最多坐 capacity 人,可以有空座。求至少需要多少辆车。输入两个整数,0 <= people <= 10^18,1 <= capacity <= 10^18。
分析推导: 需要最小整数 cars 满足 cars * capacity >= people,因此数学答案是:
\[ cars=\left\lceil\frac{people}{capacity}\right\rceil \]
不要先进行整数除法再调用 ceil,因为小数部分已经被丢掉。直接用商和余数:
#include <iostream>
using namespace std;
int main() {
long long people, capacity;
cin >> people >> capacity;
// 完整装满的车辆数,再加上“有余数时”的一辆。
// 这种写法避免 people + capacity - 1 的中间值溢出。
long long cars = people / capacity + (people % capacity != 0);
cout << cars << '\n';
}输入 10 3 输出 4;输入 0 5 输出 0。
代码解释: 商表示整车数量,非零余数意味着还要一辆车。时间、额外空间均为 \(O(1)\)。另一种写法是 (a+b-1)/b,但它多计算了一次加法。a 很大时,商加“是否有余数”的写法能避开这个中间结果。