CF985D Sand Fortress题解
xcrr
·
·
题解
不用二分，数学方法搞定
博客qwq
这道题用不上二分答案，并且需要贪心的思想。这篇题解使用贪心+数学解法，同时简单陈述二分答案的合理性。
（蒟蒻的题解，如果有疑问或者问题请指出，希望比较严谨和易懂）
看到这道题，整理一下：
-
假设这个沙堆，从左向右高度依次是 h_1,h_2,h_3,…,h_{x-1},h_{x}。这里 h_{x}=1，其余各项之间差的绝对值不大于 1。
-
-
各项和等于 n，要求 x 的值尽可能小。
思路
-
贪心思想，先说结论：h_1 尽可能大，那么 x 就尽可能小。
-
因为各项之间差的绝对值不大于 1，最后一个数还要等于 1，所以这个数列一定有从起始高度 h_1 到 1 的每一个数。
-
那么我们可以把这个数列看成这个样子：一个 h_1 到 1 的公差为 1 的等差数列，和其他零散的数。也就是把这个等差数列先拿出来。
-
现在考虑剩下的数都有哪些可能：
- 等差数列的和就是 n，剩下的数是空集。
- 等差数列的和小于 n，剩下的数在 [1,h_1] 中（因为 h_1 到 1 的每一个数都有了，所以直接加上这些数是符合题意的。
- 等差数列的和小于 n，剩下的数比 h_1 还大，它们从 h_2 开始，构成了一个先递增后递减的等差数列。
-
现在可以看出贪心结论的正确性，如果 h_1 不是尽可能大的，那么如果剩下的数在 [1,h_1] 中选（即可能 2），一定需要更多个。如果剩下的数在大于 h_1 中选（即可能 3），相当于
接下来算 $h_1$。前面的分析过后，我们直接让等差数列的和尽可能大，剩下的尽可能小。不等式：
$$
\frac{h_1(h_1+1)}{2}\leq n
$$
$$
h_1^2+h_1-2n\leq0
$$
来个图
$$
h_{1max}=\frac{-1+\sqrt{8n+1}}{2}
$$
这样已经完成了一半。**但别忘记 $h_1$ 它还有个限制：$h_1\le H$。**
于是判断一下，如果 $h_1$ 小于等于 $H$，说明 $h_1$ 取到了最大，$n$ 要么正好不剩，要么剩下的再来一个在 $[1,h_1]$ 中的数就补上了，也就是 $n$ 减一下等差数列的和，如果剩 $0$，那么 $ans$ 就是 $h_1$（项数），如果不为 $0$，那 $ans$ 就是 $h_1+1$。
如果 $h_1$ 大于 $H$ 的情况怎么办？这就说明 $h_1$ 没取到最大，就会被 $H$ 挡住，等差数列的首项是 $H$。
显然，这种情况下，我们还要额外多放几堆，这时我们的策略显然是放上面可能性的第 $3$ 种。也就是额外放置两个等差数列。设中间最高的堆为 $h_i$，我们要让 $h_1,...,h_{i-1},h_i,h_{i+1},...,h_{2i-2}$ 形成 $h_1$ 到 $h_{i-1}$ 的上升序列，和 $h_{i}$ 到 $h_{2i-2}$ 的下降序列。如图：
方程与上一个同理，两个等差数列的和为定值 $left=n-\frac{\left ( 1+H \right ) \times H}{2}$。
$$
\frac{\left ( h_1+h_{i-1} \right ) \left ( i-1 \right )}{2} +\frac{\left ( h_{i}+h_{2i-2} \right ) \left ( i-1 \right )}{2} \le left
$$
$$
\frac{\left ( H+h_{i-1} \right ) \left ( i-1 \right )}{2} +\frac{\left ( h_{i}+H+1\right ) \left ( i-1 \right )}{2} \le left
$$
$$
\left ( H+h_i \right ) \left ( i-1 \right ) \le left
$$
$$
\left ( 2H+i-1 \right ) \left ( i-1 \right ) \le left
$$
解法同上。把 $i-1$ 当成一个数化简柿子。
还有细节没完，加上这些数列，我们可能还会剩下一些数才能凑齐 $n$。 还是用 n 减一下已经算出来的和，如果剩 $0$ ，直接统计答案，否则：
剩余的大于所有已经选的最高点，我不得不多堆两个堆；
剩余的小于等于已经选的最高点，我只需多堆一个堆。
时间复杂度，显然的 $O\left ( 1 \right )$。至于为什么比一些二分跑的慢，大概是因为``sqrt``慢的原因罢。
## 参考代码
~~反正我是照着草稿纸上的柿子一点一点打的~~，建议把思路搞懂，代码就简单了。
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n;
long long h;
ll ans;
int main()
{
scanf("%lld%lld",&n,&h);
ll p=(-1+sqrt(1+8*n))/2;
if(p<=h)
{
if(n==p*(p+1)/2)ans=p;
else ans=p+1;
}
else
{
n-=h*(h+1)/2;
ll x=-h+sqrt(h*h+n);
ans=h+2*x;
if(n>x*x+2*h*x)
{
n-=x*x+2*h*x;
if(n<=h+x)ans++;
else ans+=2;
}
}
cout<<ans;
return 0;
}
```
这里我们浅说下**为什么二分答案的解法也正确？**
我们以算出来的 $h_1$ 和 $H$ 的大小关系探讨了两步，二分答案也是同样分了两步，只是和我们的求解方式不同。我们以求解 $h_1$ 的步骤举例。
看上面的上面那张图，定义域在 $x>0$ 的情况下，恰好一部分在 $x$ 轴下，一部分在 $x$ 轴上，找的是交点的值，符合二分答案的要求。
显然，两者在题目的数据范围下实际上效率相差不大（或者都能符合要求），如果出现在比赛或者测试当中，应优先写二分的方法（不易出错），数学方法用来拓宽思路较好。