我的算法书 - 整数向上取整

一句话算法

正整数除法要向上取整，只要在普通整除结果上补一个“是否有余数”的判断。

问题模型

给定正整数 a 和 b，求：

\left\lceil \frac{a}{b} \right\rceil

在 C++ 中，整数除法 a / b 默认向下取整。我们需要用纯整数运算得到向上取整，避免使用浮点数 ceil 带来的精度和类型问题。

核心直觉

把 a 除以 b：

a = q * b + r

如果 r = 0，说明刚好整除，答案是 q。

如果 r > 0，说明还剩下一段不完整的 b，也必须占一个单位，答案是 q + 1。

所以：

cpp

        1

        a / b + (a % b != 0)

这是最直观、也更不容易溢出的写法。

常见公式

竞赛中也常见这个公式：

\left\lceil \frac{a}{b} \right\rceil = \frac{a+b-1}{b}

它适用于 a, b 都是正整数的情况。

不过当 a 和 b 很大时，a + b - 1 可能溢出，所以更推荐写成：

cpp

        1

        a / b + (a % b != 0)

算法步骤

计算普通整数商 q = a / b。
计算余数 r = a % b。
如果 r == 0，说明刚好整除，答案是 q。
如果 r != 0，说明还有不足一组的剩余部分，答案是 q + 1。

合并成一行就是：

cpp

        1

        a / b + (a % b != 0)

算法证明

设：

a = qb + r,\quad 0 \le r < b

如果 $r=0$ ：

\left\lceil \frac{a}{b} \right\rceil = \left\lceil q \right\rceil = q

如果 $r>0$ ：

\frac{a}{b}=q+\frac{r}{b}

因为 $0<\frac{r}{b}<1$ ，所以：

\left\lceil q+\frac{r}{b} \right\rceil=q+1

这正好等于 a / b + (a % b != 0)。

复杂度分析

时间复杂度： $O(1)$ 。
空间复杂度： $O(1)$ 。

代码实现

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

        #include <bits/stdc++.h>
using namespace std;

using i64 = long long;

i64 ceil_div(i64 a, i64 b) {
    return a / b + (a % b != 0);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    i64 a, b;
    cin >> a >> b;
    cout << ceil_div(a, b) << '\n';
    return 0;
}

测试用例

输入：

11 5

输出：

输入：

10 5

输出：

应用分类详解

整数向上取整本质上是“把不足一组的部分也算成一组”。看到分组、分页、批次数量时都应该想到它。

一、分组与批次数

典型模式： 每组最多放 b 个，问 a 个元素需要多少组。

识别信号： 出现“每页最多”“每辆车最多”“每批最多”。

核心建模： 答案是 ceil(a / b)。

二、二分答案中的边界计算

典型模式： 给定速度、容量、时间等限制，计算是否能完成。

识别信号： 出现“每次处理 b 个”“至少需要多少次”。

核心建模： 总次数通常是若干个 ceil(work / speed) 的和。

三、数组分块

典型模式： 把长度为 n 的数组分成大小为 B 的块。

识别信号： 出现“块数”“页数”“最后一块可能不满”。

核心建模： 块数为 ceil(n / B)。

经典例题

1. 分页问题

每页最多显示 b 条记录，a 条记录需要 ceil(a/b) 页。

2. 分块数据结构

长度为 n 的序列按块长 B 分块，块数通常写成 ceil(n/B)。

3. 运输批次问题

每车最多运 b 件货物，运输 a 件货物至少需要 ceil(a/b) 车。