大伙来讨论一个算法
大家来讨论一个算法
场景：
你有一支枪，枪上有三个按键：发射、能量X2、能量/2（需要之前的发射能量是偶数）。
你面前有一队敌人，消灭每个敌人所需能量不尽相同，你可以且仅能一次设置好发射的初始能量，然后通过加倍和减半按钮来调节当前发射能量，每次发射前的发射能量均为初始设置能量。
要求：
你需要根据当前所有敌人的具体情况设置好初始能量，最少浪费能量的情况下消灭所有敌人。
敌人个数N： 1<= N <= 10000
消灭单个敌人所需能量Xi： 1 <= Xi <= 10000
示例1：
2
7 31
结果：2
示例2：
3
4 8 2
结果：0
示例说明：
示例1：第一行表示敌人个数N，第二行表示消灭每个敌人所需的能量分别为Xa=7和Xb=31，我们将枪的初始能量设置为8，消灭第一个敌人浪费1点能量，然后按X2按钮两次，发射能量变为32，消灭第二个敌人浪费1点能量。最终总共浪费2点能量，结果为2。
示例2：各行数据意义同示例1，初始能量设置为4，消灭第一个敌人浪费能量0，按X2按钮能量变为8，消灭第二个敌人浪费能量0，按/2按钮发射能量变为2，消灭第三个敌人浪费能量0。最终总共浪费0点能量，结果为0。
请给出如何设置初始能量以最少浪费能量的算法。
------解决方案--------------------
这个算法题怎么感觉像是数学上求极值的问题呢！应该要不到太复杂的数学模型能解决问题！可是，数学呀 数学。。。
------解决方案--------------------
我想了个不太高明的:
首先，能量消耗是 X，2X，4X,8X
消灭敌人所消耗的能量根据题目给出的进行一个排序获得最大值MAX
此时X的值从MAX到MIN最小值遍历，计算出消耗能量值，取最小值。（需要使用递归计算X,2X,4X。。。的值是否大于选择X）
一个for语句（J=1至MAX）
{
容器Enemy; //存储敌人的数量和消耗能量的结构体容器
for(Enemy的每个值E)
{
Y=1; //Y的值决定，1,2,4,8,16
flag = TRUE;
While（flag）
{
if(J*E*Y < 当前E)
{
Y*2；
}
else
{
flag = FALSE;
}
//计算浪费能量
}
}
}
写得比较粗，可能还有问题，大致思路讲了下。感觉肯定能优化，等大师来解答吧
------解决方案--------------------
但是我这个算法已经N^3了，希望有高人出现，我帮你推荐下吧。让更多高手看看
------解决方案--------------------
多多学习！！！
------解决方案--------------------
学习了 学习
------解决方案--------------------
是的，素数不全，是奇数的表。
------解决方案--------------------
先求最小公约数，在查表。
初始能量,为最小公约数的倍数。
算法，还是按照那个查表的计算。
表的范围是
[ 最小/最小公约数,最大值 /最小公约数]
------解决方案--------------------
我太卡了,不能引用,但是34楼的最小公约数法是有问题的
比如我下面的情况
1,2,4,5,9 敌人
1,2,4,8,16 (最小公约数和1)
0,0,0,3,7=10
3 6 12 (非公约数,非1存在比上面还小的情况)
2 1 2 1 3=9
@楼主,而且楼主说用动态规划,我没看出来动态规划能处理这们呢?
------解决方案--------------------
如果初值选择x，那么只要能表示成x*2^n + i 的数都是一样的效果
如果初值选择2，那么4 8 16 32 都是等价的
如果初值选择3，那么2 5 8 11 都是等价的
这样的话是不是可以把循环次数减少？
场景：
你有一支枪，枪上有三个按键：发射、能量X2、能量/2（需要之前的发射能量是偶数）。
你面前有一队敌人，消灭每个敌人所需能量不尽相同，你可以且仅能一次设置好发射的初始能量，然后通过加倍和减半按钮来调节当前发射能量，每次发射前的发射能量均为初始设置能量。
要求：
你需要根据当前所有敌人的具体情况设置好初始能量，最少浪费能量的情况下消灭所有敌人。
敌人个数N： 1<= N <= 10000
消灭单个敌人所需能量Xi： 1 <= Xi <= 10000
示例1：
2
7 31
结果：2
示例2：
3
4 8 2
结果：0
示例说明：
示例1：第一行表示敌人个数N，第二行表示消灭每个敌人所需的能量分别为Xa=7和Xb=31，我们将枪的初始能量设置为8，消灭第一个敌人浪费1点能量，然后按X2按钮两次，发射能量变为32，消灭第二个敌人浪费1点能量。最终总共浪费2点能量，结果为2。
示例2：各行数据意义同示例1，初始能量设置为4，消灭第一个敌人浪费能量0，按X2按钮能量变为8，消灭第二个敌人浪费能量0，按/2按钮发射能量变为2，消灭第三个敌人浪费能量0。最终总共浪费0点能量，结果为0。
请给出如何设置初始能量以最少浪费能量的算法。
------解决方案--------------------
这个算法题怎么感觉像是数学上求极值的问题呢！应该要不到太复杂的数学模型能解决问题！可是，数学呀 数学。。。
------解决方案--------------------
我想了个不太高明的:
首先，能量消耗是 X，2X，4X,8X
消灭敌人所消耗的能量根据题目给出的进行一个排序获得最大值MAX
此时X的值从MAX到MIN最小值遍历，计算出消耗能量值，取最小值。（需要使用递归计算X,2X,4X。。。的值是否大于选择X）
一个for语句（J=1至MAX）
{
容器Enemy; //存储敌人的数量和消耗能量的结构体容器
for(Enemy的每个值E)
{
Y=1; //Y的值决定，1,2,4,8,16
flag = TRUE;
While（flag）
{
if(J*E*Y < 当前E)
{
Y*2；
}
else
{
flag = FALSE;
}
//计算浪费能量
}
}
}
写得比较粗，可能还有问题，大致思路讲了下。感觉肯定能优化，等大师来解答吧
------解决方案--------------------
但是我这个算法已经N^3了，希望有高人出现，我帮你推荐下吧。让更多高手看看
------解决方案--------------------
多多学习！！！
------解决方案--------------------
学习了 学习
------解决方案--------------------
是的，素数不全，是奇数的表。
------解决方案--------------------
先求最小公约数，在查表。
初始能量,为最小公约数的倍数。
算法，还是按照那个查表的计算。
表的范围是
[ 最小/最小公约数,最大值 /最小公约数]
------解决方案--------------------
我太卡了,不能引用,但是34楼的最小公约数法是有问题的
比如我下面的情况
1,2,4,5,9 敌人
1,2,4,8,16 (最小公约数和1)
0,0,0,3,7=10
3 6 12 (非公约数,非1存在比上面还小的情况)
2 1 2 1 3=9
@楼主,而且楼主说用动态规划,我没看出来动态规划能处理这们呢?
------解决方案--------------------
如果初值选择x，那么只要能表示成x*2^n + i 的数都是一样的效果
如果初值选择2，那么4 8 16 32 都是等价的
如果初值选择3，那么2 5 8 11 都是等价的
这样的话是不是可以把循环次数减少？