剑指OFFER_剪绳子
前言
秋招临近,开始刷剑指OFFER啦,希望能在刷题中提升水平,在这个秋天顺利找到理想的工作,养家糊口哈哈:>
题目描述
给你一根长度为n的绳子,请把绳子剪成整数长的m段(m、n都是整数,n>1并且m>1),每段绳子的长度记为k[1],...,k[m]。请问k[1]x...xk[m]可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。
输入描述:
输入一个数n,意义见题面。(2 <= n <= 60)
输出描述:
输出答案。
示例1
输入
8
输出
18
思路
这道题的风格,我感觉特别像小学奥数,有点类似周长一定,问什么形状的矩形面积最大;
我的思路是,当k1、k2……加起来的和一定时,数字越集中乘积越大;
怎么表达集中这个概念呢,以上面那个周长的例子来说,就是正方形的面积最大;
所以搜索分段数量从1-number的乘积,当这个乘积下降的时候,说明达到了最大,输出即可;
然后写一个函数求出确定分段数量下的乘积,确定分段数量时,每一段都平分此绳子,遇到有余数的情况下向下取整,然后在剩余的绳子里继续平分;
代码
class Solution {
public:
int getLen(int number, int rope) {
int res = 1, tmp = 0;
while (number % rope !=0) {
tmp = number / rope;
number -= tmp;
rope--;
res *= tmp;
}
tmp = number / rope;
res *= pow(tmp, rope);
return res;
}
int cutRope(int number) {
int ans = 1;
for (int i=1; i<number; i++) {
int res = getLen(number, i);
if (res<ans)
return ans;
ans = res;
}
return 0;
}
};