2022-01-16：小明手中有n块积木，并且小明知道每块积木的重量。现在小明希望将这些积木堆起来， 要求是任意一块积木如果想堆在另一块积木上面，那么要求： 1.上面的积木重量不能小于下面的积木重量； 2.上面积木的重量减去下面积木的重量不能超过x； 3.每堆中最下面的积木没有重量要求。 现在小明有一个机会，除了这n块积木，还可以获得k块任意重量的积木。 小明希望将积木堆在一起，同时希望积木堆的数量越少越好，你能帮他找到最好的方案么？ 输入描述: 第一行三个整数n,k,x，1<=n<=200000，0<=x,k<=1000000000， 第二行n个整数，表示积木的重量，任意整数范围都在[1,1000000000]。 样例输出： 13 1 38 20 20 80 70 70 70 420 5 1 5 1 60 90 1 1 5 5 20 20 60 70 70 70 80 90 420 -> 只有1块魔法积木，x = 38。 输出：2。 解释： 两堆分别是 1 1 5 5 20 20 (50) 60 70 70 70 80 90 420 其中x是一个任意重量的积木，夹在20和60之间可以让积木继续往上搭。 来自京东面试。

答案2021-01-16：

先排序。假设没有魔法积木，求出堆数。然后求相邻堆需要的魔法积木数，魔法积木数从小到大弥合一次，堆数减1。 时间复杂度：排序的。 空间复杂度：O(N)。

代码用golang编写。代码如下：

package main

import (
    "fmt"
    "sort"
)

func main() {
    arr := []int{20, 20, 80, 70, 70, 70, 420, 5, 1, 5, 1, 60, 90}
    ret := minSplit(arr, 1, 38)
    fmt.Println(ret)
}

func minSplit(arr []int, k, x int) int {
    //Arrays.sort(arr);
    sort.Ints(arr)
    n := len(arr)
    needs := make([]int, n)
    size := 0
    splits := 1
    for i := 1; i < n; i++ {
        if arr[i]-arr[i-1] > x {
            needs[size] = arr[i] - arr[i-1]
            size++
            splits++
        }
    }
    if splits == 1 || x == 0 || k == 0 {
        return splits
    }
    // 试图去利用魔法积木，弥合堆！
    //Arrays.sort(needs, 0, size);
    sort.Ints(needs[0:size])
    for i := 0; i < size; i++ {
        need := (needs[i] - 1) / x
        if k >= need {
            splits--
            k -= need
        } else {
            break
        }
    }
    return splits
}

执行结果如下： 图片

左神javadiam