CF985D Sand Fortress
题目描述
你打算去海滩,心里想着要建造有史以来最伟大的沙堡!但海滩并不像你想象的那样是三维的,它可以被描述为一排可以堆沙柱的位置。位置从左到右编号为 $1$ 到无穷大。
显然,海滩上的沙子不够用,所以你带来了 $n$ 包沙子。令某个位置 $i$ 上沙柱的高度 $h_{i}$ 为你在该位置上使用的沙包数。你不能把一包沙子分到多个沙柱上,所有的沙子都必须用在同一个沙柱上。在第一个位置的左侧有一个高度为 $H$ 的围栏,你需要防止沙子越过这个围栏。
最终,你为建造沙堡制定了以下条件:
- $h_{1} \leq H$:最左边位置的沙子不能越过围栏;
- 对于任意 $i$,$|h_{i} - h_{i+1}| \leq 1$:相邻两个沙柱高度差过大,沙子会从高的那根流到低的那根,你不希望发生这种情况;
- $\sum h_{i} = n$:你要用完所有带来的沙子。
由于你有无限多个位置可以建造,所以总能构造出一个合法的沙堡结构。但你希望沙堡尽可能紧凑。
你的任务是计算,满足上述所有条件所需占用的最少位置数。
输入格式
一行包含两个整数 $n$ 和 $H$($1 \leq n, H \leq 10^{18}$),分别表示你带来的沙包数和围栏的高度。
输出格式
输出一个整数,表示满足所有建造条件所需占用的最少位置数。
说明/提示
以下是一些合法沙堡的高度示例:
- $n=5,H=2,[2,2,1,0,\ldots],[2,1,1,1,0,\ldots],[1,0,1,2,1,0,\ldots]$
- $n=6,H=8,[3,2,1,0,\ldots],[2,2,1,1,0,\ldots],[0,1,0,1,2,1,1,0,\ldots]$(这个例子占用了 $5$ 个位置)
对于这两种情况,第一个列表是最优答案,分别占用了 $3$ 个位置。
以下是一些不合法的例子:
- $n=5,H=2,[3,2,0,\ldots],[2,3,0,\ldots],[1,0,2,2,\ldots]$
- $n=6,H=8,[2,2,2,0,\ldots],[6,0,\ldots],[1,4,1,0,\ldots],[2,2,1,0,\ldots]$
由 ChatGPT 4.1 翻译