题目传送门
\(\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; }
首发:2022-03-22 19:55:26