整数向上取整

一句话算法

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

问题模型

给定正整数 a 和 b，求：

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

核心直觉

把 a 除以 b：

a = q * b + r

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

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

所以：

        
1

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

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

常见公式

竞赛中也常见这个公式：

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

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

        
1

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

算法步骤

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

合并成一行就是：

        
1

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

算法证明

设：

如果 $r=0$：

如果 $r>0$：

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

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

复杂度分析

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

代码实现

        
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;
}
    

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

        # 向上取整除法，逐字复刻 C++ 的 a / b（向零截断）与 a % b（余数符号随被除数）。
# 正数输入下就是常见的 (a + b - 1) / b；负数输入下 C++ 的写法并不等于数学上的 ceil，
# 这里保持一致、不做"修正"。
# 调用方保证 b != 0（C++ 除零是未定义行为，Python 会抛 ZeroDivisionError）。
# C++ 的 long long 溢出坑在 Python 不存在，int 是任意精度。


def ceil_div(a: int, b: int) -> int:
    # Python 的 // 向下取整，负数时与 C++ 的向零截断差 1，所以先按绝对值求商再补符号。
    quotient = abs(a) // abs(b)
    if (a < 0) != (b < 0):
        quotient = -quotient
    # C++ 的 a % b 就是 a - (a / b) * b，非零则商要进一。
    remainder = a - quotient * b
    return quotient + (remainder != 0)
    

测试用例

输入：

11 5

输出：

3

输入：

10 5

输出：

2

应用分类详解

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

一、分组与批次数

典型模式： 每组最多放 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) 车。