首页 > 试题广场 >

走几趟

[编程题]走几趟

热度指数：43 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

牛牛一家昨天去了百丈飞瀑漂流，所以多了很多换洗的衣物，昨天玩的非常开心，但是今天晒衣服的时候却感到一阵无奈。

在费尽九牛二虎之力之后，牛牛终于洗完了 $\mathit n$ 件衣服，但是，由于衣物上都沾着水，所以异常承重，而牛牛力气有限，一次最多可以拿起重量为 $\mathit m$ 的东西。

因此，牛牛想要知道，每次拿起衣物去阳台晾晒的重量都不超过 $\mathit m$ 的话，牛牛最少需要走几趟才能晒完所有衣服。

输入描述:

第一行输入两个正整数 ，代表衣物数量以及牛牛一次最多可以拿多重的东西。

第二行输入  个正整数 ，一次代表每件衣服的重量。

输出描述:

输出仅一行一个整数，代表牛牛最少走的趟数。

示例1

输入

3 10
3 3 3

输出

说明

三件衣物重量总和为 ，所以牛牛可以一次性拿起。

算法知识视频讲解

糖糖不甜反酸

发表于 2021-03-20 12:00:01

数据量很小，可以考虑暴搜，那我们考虑以怎样的顺序去搜索，假如每一趟用一个桶，那么就是最小需要几个桶的问题。我们可以考虑当前的衣服，1.可以放进已有的桶，2.在添加一个桶。如果不进行优化会超时的，对于第二种情况，每一个衣服都可以创建一个新桶，没有优化的余地了。对于第一种情况，我们知道搜索一般都是树形结展开全文