分糖果（JavaScript）

目录

题目描述

输入描述

输出描述

用例

题目分析

算法实现

用位运算代替Math运算

---

题目描述

小明从糖果盒中随意抓一把糖果，每次小明会取出一半的糖果分给同学们。

当糖果不能平均分配时，小明可以选择从糖果盒中（假设盒中糖果足够）取出一个糖果或放回一个糖果。

小明最少需要多少次（取出、放回和平均分配均记一次），能将手中糖果分至只剩一颗。

输入描述

抓取的糖果数（<10000000000）：15

输出描述

最少分至一颗糖果的次数：5

用例

输入

• 15

输出

• 5

1. 15+1=16;
2. 16/2=8;
3. 8/2=4;
4. 4/2=2;
5. 2/2=1;

输入

• 3

输出

• 2

1. 3-1=2
2. 2/2=1

输入

• 6

输出

• 4​​​​

1. 6-1=5
2. 5-1=4
3. 4/2=2
4. 2/2=1

题目分析

假设给定数为n，首先判定n是否为2^m，m为整数

• 若是，则不需要取出或放回，直接平均分配即可，总次数即平均分配次数m。
• 若不是，则说明n不能直接平分分配，此时我们需要取出一些糖果或放回一些糖果，来让n可以直接分配，即让n = 2^m，m为整数。

这里如何让n变为2^m呢？比如n=6，它有两种选择

1. 变为4，即放回两个糖果
2. 变为8，即取出两个糖果

• 此时n就是2^m了，可以直接分配了
• 那么n=6如何知道变为4或8呢？其实很简单，看下图即可
•  之后，就是比较到底是取出糖果总次数少，还是放回糖果总次数少，取最少的就行

算法实现

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");
 
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
 
rl.on("line", (line) => {
  console.log(distribute(line));
});
 
/* 分糖果 */
function distribute(count) {
  if (count === 0) {
    return 0;
  }
 
  // 取count底数为2的幂
  const pow = Math.log2(count);
  // 如果幂是整数，表示可以直接平均分配，所以此时幂就是总次数
  if (Number.isInteger(pow)) {
    return pow;
  }
 
  // 如果幂不是整数，则表示无法直接平分，所以分别获取幂的ceil值和floor值
  const ceil_pow = Math.ceil(pow);
  const floor_pow = Math.floor(pow);
 
  const ceil_count = Math.pow(2, ceil_pow);
  const floor_count = Math.pow(2, floor_pow);
 
  // ceil_diff表示要取出多少次糖果，floor_diff表示要放回多少次糖果
  const ceil_diff = Math.abs(ceil_count - count);
  const floor_diff = Math.abs(floor_count - count);
 
  return Math.min(ceil_pow + ceil_diff, floor_pow + floor_diff);
}

用位运算代替Math运算

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");
 
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
 
rl.on("line", (line) => {
  console.log(distribute(line));
});
 
/* 分糖果 */
function distribute(inputCount) {
  inputCount = parseInt(inputCount);
  if (inputCount === 0) return 0;
 
  let k = inputCount - 1;
  k |= k >>> 1;
  k |= k >>> 2;
  k |= k >>> 4;
  k |= k >>> 8;
  k |= k >>> 16;
  let max = k + 1;
  let min = max / 2;
  let n = inputCount - min > max - inputCount ? max : min;
  let count = Math.min(inputCount - min, max - inputCount);
  while (n != 1) {
    n = n / 2;
    count++;
  }
  return count;
}

 上面这个算法采用了位运算，速度要比基于Math方法运算快40%左右。

下面这段代码的作用是获取inputCount的最近的2^m，比如inputCount=6，则下面代码的max值最终为8。

  let k = inputCount - 1;
  k |= k >>> 1;
  k |= k >>> 2;
  k |= k >>> 4;
  k |= k >>> 8;
  k |= k >>> 16;

  let max = k + 1;

等价于上一个算法中ceil_count ，

const pow = Math.log2(count);

const ceil_pow = Math.ceil(pow);

const ceil_count = Math.pow(2, ceil_pow);

 后面的逻辑就差不多了。