g5-09156. 补种树苗 未做

护坡林带沿道路数轴栽了 $n$ 棵树,第 $i$ 棵位于坐标 $x_i$,坐标互不相同,输入可能乱序。验收要求任意相邻两棵树之间的间距都不超过 $d$,空档过大的地段必须补种,补种只能在已有树木之间的空档里进行。补一棵算一棵,请求出最少需要补种多少棵;若不超过预算 $B$ 棵,第二行输出 YES,否则输出 NO。

第一行三个整数 $n,d,B$。
第二行 $n$ 个互不相同的整数 $x_i$,顺序任意。

第一行一个整数,表示最少补种数量。
第二行输出 YES 或 NO。

排序后坐标为 $0,7,8,20$,相邻空档长 $7,1,12$。长 $7$ 的空档至少补 $2$ 棵:补 $1$ 棵会把 $7$ 分成两段,两段之和为 $7$,必有一段超过 $3$;补 $2$ 棵(如种在 $3$ 与 $6$)可得间距 $3,3,1$,可行。长 $1$ 的空档无需补。长 $12$ 的空档至少补 $\lceil 12/3\rceil -1=3$ 棵(如种在 $11,14,17$,间距 $3,3,3,3$;只补 $2$ 棵时三段之和为 $12$,必有一段超过 $3$)。合计 $2+0+3=5$ 棵,超过预算 $2$,故输出 $5$ 与 NO。

$1\le n\le 2\times 10^5$;$1\le d\le 10^9$;$1\le B\le 10^9$;$0\le x_i\le 10^9$ 且互不相同。