选择结构+特判 —— P5709 Apples Prologue

超级玛丽王子 · 2020-08-15 09:34:59 · 个人记录

这道题乍一看似乎很简单，思路清晰，给定 m 个苹果，s 分钟，t 分钟吃一个，那么 s 分钟就能吃 \lfloor\dfrac s t\rfloor 个苹果，剩下 m-\lfloor\dfrac s t\rfloor 个苹果。

但是！但是！但是！

这道题目有不少坑点，下面一一解释。

如果 t=0，那么老八吃 1 个苹果要 0 秒，吃 m 个苹果自然也要 0 秒，所以苹果 1 个都不会剩下，应该输出 0。但是，由于除以 0 是非法的运算，这里需要特判；
题目要求的是完整的苹果，因此老八吃掉的数量应该改为 \lceil\dfrac s t\rceil 个苹果。最后剩下 m-\lceil\dfrac s t\rceil 个苹果。

这里给大家介绍一种不使用 STL 的 ceil 函数完成向上取整的运算（以下计算全部应用整数截断，即 a,\ b 均为整数时的效果）：
\lceil \dfrac a b \rceil = \dfrac{a-1} b+1
简单证明一下：
1. 当 a \mid b 时，\lceil \dfrac a b \rceil=\dfrac a b；令 \dfrac a b\equiv q (注：这里 \equiv 不是同余符号，而是 令...为... 的意思）。按照整数截断原则，\dfrac {a-1} b=q-1，所以 \dfrac {a-1} b+1=q=\lceil\dfrac a b\rceil；
2. 当 a \nmid b 时，将 a 减 1 不会影响到最后经过整数截断的商的值（因为只是对余数进行了运算），而易得本例中 \lceil \dfrac a b \rceil=\dfrac a b +1，故 \lceil \dfrac {a-1} b \rceil = \lceil \dfrac a b \rceil=\dfrac a b +1=\dfrac {a-1} b+1，证毕。
苹果剩下的个数显然不可能是负数，所以如果老八把苹果吃完了要输出 0，这里我们用 max 函数来实现。

最后贴代码：

#include <bits/stdc++.h>
using namespace std;
int main(void) {
    int m,t,s;
    cin>>m>>t>>s;
    if(!t) cout<<0;
    else cout<<max(m-((s-1)/t+1),0);
    return 0;
}

完结撒花~

选择结构+特判 —— P5709 Apples Prologue

但是！ 但是！ 但是！

但是！但是！但是！