C/C++教程

CF402A 题解

本文主要是介绍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

这篇关于CF402A 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!