『Codeforces 985D』Sand Fortress

Problem

窝不想抄题目了…

题目描述：

你有$n$堆沙子，最左边的沙子的最大高度不能超过$H$，让你在一个从$1$到$\infty$的一维平面内放沙子，且要满足相邻两个坐标的沙子的高度不能超过$1$。问沙子能够占用的最少坐标点的个数。

Solution

因为题目要求相邻两个坐标的沙子高度不能超过$1$，这代表最后一堆沙子的个数也必定为$1$。

而题目要我们求占用坐标点的最少个数，根据贪心的思想，要使占用的点最少，则我们必须要贪心地令沙子的高度尽可能高。

• 因为最后一堆的沙子的个数为$1$，所以沙子的高度所形成的曲线必定是先增后减的或者一直减小的曲线。

  • 沙子的高度存在单调性！
  • 二分答案

  • 不断二分占用坐标的个数即可。

    而二分的$\rm check$函数，我们因为最优的情况下，两两沙堆相差均为$1$，因此我们可以运用等差数列求和公式求出总的沙子堆数，并用它与$n$进行对比进行二分即可。

    值得一提的是，当枚举出$n$为奇数的时候，会出现有两个坐标的值均相当的情况，需要注意

Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, h;
const ll cnt = 2000000000;
inline bool check(const ll &x)
{
	if (x <= h)
	{
		if (x >= cnt) return true;
		return (x * (x + 1) >> 1) >= n;
	}
	register ll a = ((x - h) >> 1) + h;
	if (a >= cnt) return true;
	if ((x - h) & 1)
		return ((a * (a + 1) >> 1) + ((a + h) * (a + 1 - h) >> 1)) >= n;
	return ((a * (a + 1) >> 1) + ((a - 1 + h) * (a - h) >> 1)) >= n;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> h;
	register ll ln = 1, rn = n;
	while (ln <= rn)
	{
		ll mid = (ln + rn) >> 1ll;
		if (check(mid)) rn = mid - 1;
		else ln = mid + 1;
	}
	cout << rn + 1;
	return 0;
}