大家来讨论一个算法

Question

我想了个不太高明的:
首先，能量消耗是    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;
             }             //计算浪费能量
         }
     }
}写得比较粗，可能还有问题，大致思路讲了下。感觉肯定能优化，等大师来解答吧

Answer 1

感觉算法挺简单的，数值范围因为不大（小于10000），我们把题目做一下简单的数学变化：因为不允许非整数的存在，实际问题就转变为需要找一个质数（素数）X，使得 X*(2^n)形成一个数的序列，再用题目输入给定的敌人的血量去求差，使得差的和最小。由于数据量不大，我们可以先将10000以内的素数全部计算形成表，然后挨个用这个表去对应题目的输入，对于输入的每个数，去表里找比这个数大的数相减，取最小值。计算复杂读O(n)可能上面没描述得特别清楚，我根据题目给定的例子举例一下：对于素数2，形成表： 1、2、4、8、16……
对于素数3:，形成表：3、6、12、……
对于素数5，形成表：5、10、20、……
对于素数7，形成表：7、14、28、……对于示例1,（7、31），我们遍历以上表，每个数取表里比他大的那个数去相减，得出
素数2的表 sum= (8-7) + (32-31) = 2
素数3的表 sum=(12-7) + (48-31) = 22
……所以最小值为2

Answer 2

需要进一步优化算法的话，可以在素数形成的表上做二分查找。
算法复杂度其实大概是 O(n logm)，还有很多地方可以优化。

Answer 3

对于这个问题，当 1<= N <= 1000000, 1<= Xi <= 10000时，是存在1秒钟内完成任务的解决方法的。
希望能有高手帮助解决。

Answer 4

更正一下：当 1<= N <= 1000000, 1<= Xi <= 1000000时，是存在1秒钟内完成任务的解决方法的。

Answer 5

提示：需要用到排序（Sorting）、搜索（Searching Technique）、分治算法（Divide and Conquer）和动态规划（Dynamic Programming）。

Answer 6

如果初值选择x，那么只要能表示成x*2^n + i 的数都是一样的效果
如果初值选择2，那么4 8 16 32 都是等价的
如果初值选择3，那么2 5  8 11 都是等价的 
这样的话是不是可以把循环次数减少？

Answer 7

这个数量级我觉得我的算法也非常轻而易举。有OJ上有这道题么？不是哪个OJ上的，是一个国外的朋友问的。
我尝试预先生成了一个奇数倍增表，如果是百万级别的，那么这个表就有50万行。
你觉得1秒完成的把握大吗？有什么精神我还没有领会呢？