CF402A 题解

标签：最大化 箱子 隔板 color 题解 d% 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;
}

首发：2022-03-22 19:55:26

标签：最大化,箱子,隔板,color,题解,d%,CF402A
From： https://www.cnblogs.com/liangbowen/p/16622815.html