前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >剪绳子得到最大乘积

剪绳子得到最大乘积

作者头像
名字是乱打的
发布2021-12-22 15:01:57
2630
发布2021-12-22 15:01:57
举报
文章被收录于专栏:软件工程软件工程

题目描述

给你一根长度为n的绳子,请把绳子剪成整数长的m段(m、n都是整数,n>1并且m>1),每段绳子的长度记为k[0],k[1],...,k[m]。 请问k[0]xk[1]x...xk[m]可能的最大乘积是多少? 例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。

代码思路:

实际上分割的绳子在大于3的情况下,每个绳子只能分为a个2或者b个3 因为大于3的数字都可以用2,3来表示,比如4=22+03,,5=12+13,11=12+33 而且,3比2大所以我们在做乘法时候,只用考虑,程序中有几个三,几个2即可, 我们需要让3尽可能的多,对于大于3的数,我们%3,最大值是2 这样我们在target大于3的时候

  • 如果target%3==2,我们可以用剩一个2,其余用3,相乘
  • 如果target%3==1,我们需要剩两个2,因为31<22
  • 如果target%3==0,则可以用全部都是3的组合来做乘积

代码:

代码语言:javascript
复制
 public static int cutRope(int target) {
        //对于大于3的数在分割都是可以分为a个2和b个3相加的,比如4=2*2,5=2+3,6=3+3
        if (target < 2)
            return 0;
        if (target==2){//1,1
            return 1;
        }
        if (target==3){//1,2
            return 2;
        }
        if (target%3==2){
            return (int) (Math.pow(3,target/3)*2);//剩一个2
        }
        if (target%3==1){
            return (int) (Math.pow(3,target/3-1)*2*2);//省一个1话,我们而已少算一个3,算两个2相乘,因为3*1<2*2
        }
        return (int)Math.pow(3, target/3);//可以分为全是3的情况
    }

小提醒

如果你做的是牛客的算法的话,他对电脑自动输入流有一定限制,牛客采用的是一种读本地文本做测试的方法.所以他们用的不是我们用的Scanner,而是我们需要去指定一个磁盘输入流,按行获取数值进行输入 如:

代码语言:javascript
复制
 public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        System.out.println(cutRope(n));
    }
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019/12/17 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
    • 代码思路:
    • 代码:
    • 小提醒
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档