二分答案.
把 $n$ 个物品摆成一排,一个位置上可以放多个物品,但要满足两个限制.
- 第一个位置上放的物品数目不能超过 $H$ .
- 任意两个相邻位置上放的物品数目之差必须 $\le 1$ ,这个规则对于最后一个位置也适用,即最后一个位置必须恰好放 $1$ 个物品.
求出摆下这 $n$ 个物品至少需要的位置数目.
首先需要注意到答案是可以二分的,因为差值可以为 $0$ ,所以多出来的位置总可以通过调整得到合法解.
考虑二分一个答案 $k$ ,于是需要求出 $k$ 个位置最多能放下的物品数目.
由于最后一个位置必须是 $1$ ,且第一个位置的所以 $k$ 个位置最优的方案一定是先上升,再下降到 $1$ .
感性理解一下.
判断一下直接这样放,第一个元素的位置是不是 $\le H$ 的,否则就只能从 $H$ 开始依次递减摆放.
如果二分答案的上界设为 $n$ ,对等差数列求和时会爆掉 $\rm long\ long$ .
可以对称的放,即高度从 $1$ 到某个 $x$ ,再到 $1$ .于是可以将上界设到 $2\sqrt n$ .
1 | //%std |