聚光科技的笔试题目
有10000根长短不一的木桩，而且每根木桩的长度都是一个整数，要把这10000根木桩切成30000根相同的木桩，而且长度都为整数，求解最大的长度。（10000根木桩的长度已知）
[解决办法]
所有木桩长度取最大公约数
[解决办法]
最长的那根可能切成N段，而最短的可能根本不切
[解决办法]
穷举
count = 10000
max_length = getMaxLength();
for i = max_length; i > 0; i--
count = 0;
for j = 0; j < count; j++
count += array[j] / i;
if count > = 30000
break;
return i;
[解决办法]
被切下来的长度应该在最短的1／3和最长那根的1／3之间，数不大，穷举
[解决办法]
先把10000根木棍按长度排序，从小到大存储在数组中
假设最大长度为MAX,那么就从MAX/3开始往下搜索，在搜索的过程中使用分支界限（可大大降低运算时间）
[解决办法]
如果先将数组从大到小排序，则可在循环中有以下判断：
if (count > = 30000) 长度可以
if (i > count/3) 长度过长
[解决办法]
切成30000根相同的木桩
这里的“相同”是什么意思？长度相同？
1. 如果不是长度相同: 把木桩从短到大排序，从最短木桩开始累加木桩长度;如果累加到最后条木桩之前有累加的木桩长度==3w,那么所求长度=最后条木桩长度;如果累加到最后条木桩，那么所求长度 N = (3w-累加的长度)/最后条木桩长度,如果N <1那么N=0
2.如果要长度都相同，那么就是求所有木桩长度的最大公约数,再看如此切分能否达到3w数量
[解决办法]
这道题目 是否复杂看条件
条件：能否有多余的木棍。比如10000根 里面 我只从500根里面就砍出了30000根。
而且我舍弃了 多余的9500根 和500根里面多余的木棍
这个难度比较大的。而且很复杂。
需要从最短的长度 1/3=> 第二长度进行一次测试。复杂度太大了。比如
1-9999 的长度 也是1-9999 而第10000 是10^10 长度。就会出现这样的情况。
[解决办法]
实际上就是解个方程组，假设最后每根木桩长度是 x，用L[i]表示第i根木桩的长度，那么 x 必须满足 SUM( L[i]/x )=30000
x 的取值范围是 0 <= x <= SUM(L[i])/30000
int x = 0;
for ( int i=0; i <10000; ++i ) x += L[i];
if ( x < 30000 ) return 0; // 10000根木桩加起来的总长度都没有30000还砍啥
x /= 30000;
bool success = false;
do
{
int count=0;
for(int i=0;; ++i)
{
count += L[i]/x;
// 1. 砍完第 10000 根后，刚好 30000 段
if ( count == 30000 && i == 9999 )
{
success = true;
break;
}
// 2. 砍完第 10000 根后，多于 30000 段
// 如果发生这种情况，说明砍完第 9999 根的时候还不到 30000 段，
// 说明没有适合刚好砍到 30000 段的解，再减小长度肯定只能砍出更多段来。。。
if ( count > 30000 && i == 9999 )
{
// 要不要特殊处理你看着办，如果不需要特殊处理的话可以跟上面的情况合并在一起
success = true;
break;
}
// 3. 还没砍到 10000 根就满了 30000 段
// 这说明最大长度就是 x，也只能这样处理...
if ( count > = 30000 ) // 砍完第 10000 根的情况上面已经处理了，这里不用再判断 i
{
return x; // 直接返回 x
}
// 4. 还没到 30000 根，但是木头已经砍完了。。。
if ( i == 9999 )
{
--x; // 测试下一个最短长度...
if ( x == 0 ); return 0;
i = 0; count = 0; //重置循环
}
// 5. 没到 30000 段，木头也没砍完，继续...
}
}while ( !success );
应该就是这样了。。。
[解决办法]
mark
