新年的巧克力棒

马上就要到羊年了, 羊村一片欢腾, 懒羊羊则懒洋洋地躺在草坪上吃新年的巧克力棒.

他手上的巧克力棒是个由n个巧克力单元格组成的长度为n的长条, 现在懒羊羊想把巧克力棒掰开成一个个小单元格.

初始时懒羊羊会把这根巧克力棒丢在草坪上, 然后每次懒羊羊会从草坪上拿起一根长度大于1的巧克力棒, 然后从某两个相邻的单元格的间隙处掰开变成两根巧克力棒, 然后把这两根巧克力棒丢在草坪上. 懒羊羊初始愉悦值为0. 每次掰开巧克力棒后如果这两根巧克力棒长度相等, 那么懒羊羊将提升1点愉悦值.

当然, 草坪上全是长度为1的巧克力棒时懒羊羊就会停止操作. 现在懒羊羊想知道, 他能获得的愉悦值最多是多少?

说明

• 对于n=1, 初始时草坪上已经全是长度为1的了, 所以愉悦值为0.
• 对于n=3, 懒羊羊可以先把它掰开变成一根长度为1的和一根长度为2的巧克力棒; 然后再把长度为2的巧克力棒从正中间掰开获得 1点愉悦值, 所以答案是1.
• 对于n=4, 懒羊羊可以先从正中间掰开变成两根长度为2的巧克力棒, 获得1点愉悦值; 然后再对于每根长度为2 的巧克力棒从正中间掰开各获得1点愉悦值, 所以答案是3.
• 1<=n<=10^9.

题解

1. 对每一块巧克力棒(长为len), 找到最大的k使得2^k <= len. 将巧克力棒掰开为2^k和len-2^k两部分.
2. 对于2^k的部分, 可以满足每次都能恰好掰开使得两部分长度相等, 从而整体获得2^k-1点愉悦值.
3. 对于len-2^k的部分:
   • 如果len-2^k为0或1, 则不需要再操作.
   • 否则, 重复步骤1.

fn solution(mut length: u32) -> u32 {
    let mut sat = 0;
    while length > 1 {
        let perf = length.ilog2();
        let perf_part = 2u32.pow(perf);
        sat += perf_part - 1;
        length -= perf_part;
    }
    sat
}
 
#[test]
fn test() {
    let cases = vec![
        (1, 0),
        (3, 1),
        (4, 3),
        (7, 4),
        (233333333, 233333319),
    ];
 
    for case in cases {
        let tobe = case.1;
        let got = solution(case.0);
        println!("f({}) tobe {tobe}, got {got} -- {}", case.0, tobe == got);
    }
}

论证

个人理解, 仅供参考.

转换为等价问题: 初始有n份大小为1单位的材料, 任意两份相同大小的材料可以融合成一份两倍大小的材料, 现对材料进行融合操作直到无法继续, 求最终的融合情况 (即各部分的大小). 可以根据最终的融合情况得到本题所求的最大愉悦值.

等价性

• 本题中巧克力棒每次掰开为相同大小的两份即可获得1愉悦值, 等价于材料融合时每次融合可以获得1愉悦值.
• 本题中每次非等分时无法获得愉悦值, 等价于不同大小的材料无法融合.

等价求解

结论1: 最终融合情况中无重复值.

• 若存在两份大小相同的材料, 则可以将其融合得到一份两倍大小的材料, 与操作的终止条件矛盾. 所以最终融合情况中无重复值.

结论2: 对于等价问题, 可以证明最终的融合情况的唯一性. (即最终各材料大小排序后组成的有序序列是唯一的)

• 对于n = 1, 显然结果序列为result = [1], 唯一.
• 假设对于n = k的情况, 结果序列为result = [size1, size2, ..., sizek](从小到大排序), 唯一.
• 当n = k + 1时, 先对其中的k进行操作得到结果result = [size1, size2, ..., sizek](从小到大排序). 对于剩下的大小为a 的材料 (初始a = 1):
  • 情况1: 若result[0] > a, 则最终结果result = [a, size1, size2, ..., sizek]是唯一的.
  • 情况2: 若result[0] = a, 则将a与size1融合得到a=2*size1, 重复上述操作直到进入情况1.
• 所以最终的融合情况是唯一的.

结论3: 对于n份材料, 所能得到的最大融合材料的大小sizemax 为 2^k (其中2^k <= n且2^(k+1) > n).

• 证明2^k: 相同材料融合时, 材料大小*2, 初始材料大小为1, 所以最大融合材料的大小为2的幂.
• 证明2^k <= n: 由于材料总量为n, 所以最大融合材料的大小不会超过n.
• 证明2^(k+1) > n: 假设2^(k+1) <= n, 则此时能够找到2份大小为2^k的材料, 从而可以继续融合, 与操作的终止条件矛盾. 所以2^(k+1) > n.

根据结论2, 可以每次先求解最大融合材料的大小:

• 对于n份材料, 最大融合材料的大小为2^k记为sizek.
• 将2^k大小的材料融合后, 剩下的材料大小为n - 2^k.
• 重复上述步骤, 得到最终的融合情况result = [size1, size2, ..., sizek].

结果转换

对于大小为sizei的材料(sizei>1), 将其等分并放回, 重复此操作直到得到sizei份大小为1的材料, 这个过程中的每一次操作都可以获得 1愉悦值.

操作次数op(i) = sizei - 1. 所以最终总的愉悦值为op(1) + op(2) + ... + op(k) = size1 + size2 + ... + sizek - k = n - k (k为result的长度).

观察易得: k 等于 n 的二进制表示中 1 的个数. (使用示例说明)

// 示例1
  0b10101 (n)
= 0b00001 (size1)
+ 0b00100 (size2)
+ 0b10000 (size3)
 
// 示例2
  0b11011 (n)
= 0b00001 (size1)
+ 0b00010 (size2)
+ 0b01000 (size3)
+ 0b10000 (size4)

优化题解

根据结果转换部分的结论, 可以直接求解n的二进制表示中1的个数, 从而得到最终的愉悦值.

fn solution(n: u32) -> u32 {
    n - n.count_ones()
}
 
#[test]
fn test() {
    let cases = vec![
        (1, 0),
        (3, 1),
        (4, 3),
        (7, 4),
        (233333333, 233333319),
    ];
 
    for case in cases {
        let tobe = case.1;
        let got = solution(case.0);
        println!("f({}) tobe {tobe}, got {got} -- {}", case.0, tobe == got);
    }
}

References

• #66. 新年的巧克力棒
• vfleaking 的题解