题解

思路

若购买长度为 $n+1$ 的圆木，并用它切出长度为 $1,2,\ldots,k$ 的圆木，必须有 $1+2+\cdots+k\le n+1$。

做法

取满足该不等式的最大 $k$，再直接购买长度为 $k+1,k+2,\ldots,n$ 的圆木，总花费为 $n-k+1$。任何更便宜的方案都必须用某根已购买的圆木代替更多的短圆木，而长度 $n+1$ 最大，能代替的最短前缀最长，因此上述方案最优。

在 $[0,n+1]$ 上二分最大的 $k$，判定 $k(k+1)/2\le n+1$。乘法使用 __int128 避免溢出。

复杂度

时间复杂度为 $O(\log n)$，空间复杂度为 $O(1)$。