网站建设合同 包括什么,免费html网页模板,无锡建设管理服务中心,深圳住房和建设局网站 宝安目录
题目#xff1a;
示例#xff1a;
分析#xff1a;
代码#xff1a; 题目#xff1a; 示例#xff1a; 分析#xff1a;
给我们一笔钱和一些小朋友#xff0c;要我们把这些钱分完不能剩#xff0c;并且不能有小朋友被分到4元以及每个人至少分到1元#xff…目录
题目
示例
分析
代码 题目 示例 分析
给我们一笔钱和一些小朋友要我们把这些钱分完不能剩并且不能有小朋友被分到4元以及每个人至少分到1元问我们能给多少个小朋友正好发8元。
这道题让我挺意外的因为明明是个简单题但是截止我做题的时候通过率只有二十多比大多数题都要低所以这题还是值得说一说的。
这道题主要是需要分类讨论首先条件有每个小孩子都至少要分1元因此如果钱数比小朋友更少那么无法分配返回-1。
题目要我们尽可能多的让小朋友分到8元因此如果钱数大于小朋友的数量乘8那么最优策略是
给所有小朋友8元剩下的钱都塞给某个小朋友这样分到8元的小朋友数量就是小朋友数量-1。
两个极端情况分析完剩下就是不能给小朋友分4元。
我们需要尽可能多的分8元因此我们的策略是先给每个人分1元拿个低保然后一个个的塞钱直到分到了8元再接着给下一个小朋友塞钱。
如果我们分完钱的时候刚好给小朋友分到4元那么我们需要避免这种情况因此我们可以把4元拿回来1元塞到另一个只分到1元的小朋友手上。如果其他没有拿1元的小朋友了就把这1元塞给拿到8元的某个小朋友手上此时拿到8元的小朋友数量就是原本小朋友数量-2。
其他情况我们可以直接模拟给每个小朋友都先分1元然后还能给几个小朋友分7元写成表达式就是m-n/7刚刚上面给小朋友分到4元但是其他还有分1元的小朋友的情况也可以这么算出来。 代码
class Solution {
public:int distMoney(int money, int children) {//不够分一元if(moneychildren) return -1;//每个人都至少能分8元,挑出一人分8元以上 if(moneychildren*8) return children-1;//特殊情况,最后1人分到4美元,改成其中一个分8元的改成分到8,最后一人4if(money(children-1)*84) return children-2;//给每人发一元之后再看看能给多少人再发7元return (money-children)/7;}
};
