CF402A 题解

题目传送门

\color{red}{see}\space \color{blue}{in}\space \color{green}{my}\space \color{purple}{blog}

小学生又双叒叕来写题解啦！

看到其他题解描述得并不清晰，我就来一发。

这道题实际上不困难，重点就是贪心。

只要遵循“能用隔板就用隔板，尽量将一个箱子所能装的坚果数最大化”的原则就好。

我们试着在一个箱子里塞尽可能多的隔板。

具体看这一部分代码：

if (b >= k - 1)  
//贪心，能用隔板就用隔板，尽量将一个箱子所能装的坚果数最大化。 
{
    b -= (k - 1);
    a -= k * v;   
}
else
{
    //隔板不够，为了最大化，就将全部隔板都塞进去。
    a -= (b + 1) * v;
    b = 0;
}

细心的童鞋会想到 a 这样减后不是可能会出现负数吗？

你想啊，a 既然能达到负数，那 a = 0 不就更能达到了吗！

所以并不需要特判什么的，一直循环，只需要在 a \le 0 时停止循环并输出答案就完事了。

最后给出完整代码：

#include <iostream>
#include <cstdio>
using namespace std;

int main()
{
    int k, a, b, v, cnt = 0;  //cnt 记录箱子的数量。 
    scanf("%d%d%d%d", &k, &a, &b, &v);
    while (true)
    {
        cnt++;
        if (b >= k - 1)  
        //贪心，能用隔板就用隔板，尽量将一个箱子所能装的坚果数最大化。 
        {
            b -= (k - 1);
            a -= k * v;   
        }
        else
        {
            //隔板不够，为了最大化，就将全部隔板都塞进去。
            a -= (b + 1) * v;
            b = 0;
        }
        //实际上，此时的 a 有可能为负数，但这显然不重要。 
        if (a <= 0) break;
    }
    printf("%d", cnt);
    return 0;
}