java - 甜蜜分配(优化)

Question

You got starting amount of Sweets provided suppose N, you are provided T such that every time you distribute T sweets from N, 1 sweet is added. Determine the number of sweets you can distribute.

例如。 N=5 , T=2

• 第一步:分发5-2+1颗糖果:2颗剩余糖果:4颗
• Step2:分发4-2+1颗糖果:2颗剩余糖果:3颗
• Step3:分发3-2+1颗糖果:2颗剩余糖果:2颗
• Step4:分发2-2+1颗糖果:2颗剩余糖果:1颗

• Step5:分发1个糖果:1个剩余糖果:0

  代码返回:总甜度:9

我的代码如下:

    public static int countSweets(int n, int t) {
       //recursive code is commented
       /*if(n<t)
         return n;
        return t+countCandies(n-t+1,t);*/

     //simple while loop snippet
       int count=0;
       while(n>=t)
       {
         count=count+t;
         n=n-t+1;
       }
       return count+n;
    }

我尝试了简单的和递归的两种方法。显示的错误是

1. 简单:超过时间限制
2. 递归:堆栈溢出(n 和 t 之间的较大差异)

Answer 1

使用除以 T 而不是减去 T。对于 N=5，T=2:

1. 5/2 = 2 次分配=2 次奖励元素和 1 次剩余元素
2. 3/2 = 1 次分配=1 次奖励和 1 次剩余
3. 2/2 = 1 次分配=1 次奖励和 0 次剩余
4. 1/2 = 0 - 部分分配，0 个奖励项目

最终计数= N+ 奖励元素 = 5+2+1+1+0 = 9

在这个例子中它只快了 1 步，但对于大 N 来说它会更重要。