每日leetcode第0077天 0517. Super Washing Machines

这是一道特别有意思的题目。

自己可以尝试多举几个数字来尝试。

这样我们就可以得到最佳的策略。甚至可以自己写一个模拟算法。

考虑到每一次每一个洗衣机可以向左右丢一件,每一台洗衣机可以最多接受两件。

所以麻烦的是丢的,而不是接的。

 

如果是模拟算法,我们需要怎么判断往哪里丢呢。

比如3 7 4 6,目标是集体变5。

7必然要往左丢,因为左边的平均值低于目标。

而右边平均值等于目标,就不需要往右边丢了。

丢了还得收回来,这不扯淡么。

又比如1 6 2,那么应该怎么丢呢?

其实就是中间那个往两边都得丢,先往左还是右有差吗?

没差,因为反正要丢3次。

2 0 11 0 2,如果像这样左右会有0导致无法一次性传递到两边,怎么办?

其实完全不用担心,只需要保证每一次都尽力往外传往外丢就可以了。

这个情况也就是丢11-目标值3,也就是8次。

 

弄清楚模拟算法后,我们就可以用贪心算法了。

直接看哪个比目标多得最多,多余的值输出就可以了。



关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。