当各段绳子相等时,乘积最大,所以主思路就是尽量让各段绳子长度相等

剪绳子

http://www.nowcoder.com/questionTerminal/57d85990ba5b440ab888fc72b0751bf8

思路:
当各段绳子相等时,乘积最大,所以主思路就是尽量让各段绳子长度相等;
然后,遍历截取各段的情况,最后去最大值;

当绳子长度能被绳子段数整除时,乘积就是各除数的乘积;
当绳子长度不能被绳子段数整除时, 取靠近 n / m 的整数,这里是 ceiling(n/m),因为还有一个余数,不然截断后绳子数量会变成 m+1。

class Solution {
public:
    int cutRope(int number) {
        int maxMul = 0;
        for(int m = 2; m <= number; ++m)
        {
            int mul = 1;
            if(number % m == 0)
            {
                for(int i = 0; i < m; ++i)
                {
                    mul *= number / m;
                }
            }
            else
            {
                int factor = number / m + 1;
                for(int i = 0; i < m - 1; ++i)
                {
                    mul *= factor;
                }
                int sum = factor * (m - 1);
                mul *= (number - sum);
            }

            maxMul = max(mul, maxMul);
        }

        return maxMul;
    }
};
全部评论

相关推荐

bg27强双非本,目前在学习golang后端gin框架部分,在b站找了一个轮子项目敲了一下,技术栈是gin&nbsp;+&nbsp;gorm&nbsp;+&nbsp;mysql&nbsp;+&nbsp;redis。我目前的想法是这一个月学习408和go八股以及刷算法然后在12月找个寒假实习然后大三下开始准备考研。我是考研意愿比较强烈,想问一下我是应该all&nbsp;in其中一个方向吗,我感觉我实习对我考研来说也是没什么帮助的好像。
牛客28967172...:毕业工作,考研,考公是完全不同的方向。 99%的人拼尽全力也只能把一个做好(能做好都已经是佼佼者了,比如进进大厂,考985或者考公) 如果你确定要考研可以不用学任何就业技术框架,也不用实习经验,刷题背知识点就行,但注意必须考92院校起步,因为这个年代双非硕毕业后完全不如双非本(互联网行业),可以说双非硕在互联网就业完全是负收益
投递哔哩哔哩等公司10个岗位
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务