题目描述
给你一根长度为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的组合来做乘积
代码:
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,而是我们需要去指定一个磁盘输入流,按行获取数值进行输入
如:
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));
}
