『二分答案·贪心』四校联考：积木大赛

$\mathrm{Problem}$Problem

为了庆祝国庆，厦门一中举办了一年一度的“积木大赛”。

在2013年NOIP大赛中，夏夏同学己经搭建了宽度为n的大厦，其中第i块高度为hi。今年比赛的内容是对其NOIP2013搭建大厦进行扩建，使用的材料也都是体积为1正方体积木。

今年搭建的规则是：如果要在某一个位置上放一个积木，必须满足它的左下、下方、右下都有积木（用二维坐标a表示，如果要在a[i,j]位置放积木,那么a[i-1,j-1]、a[i,j-1]、a[i+1,j-1]必须要有积木）。

如果搭的积木大厦越高，夏夏同学就会觉得越有成就感，现有m个积木，问你能搭建的最大高度是多少？

100%的数据满足：n<=100,000;m<=1000,000,000。

$\mathrm{Solution}$Solution

这道题目好难啊，居然放在了模拟赛的第一题（还好不是考试）…

由于高度位置，我们在确定了这个最高点的时候我们也不知道具体的高度应该使用多少，因此我们使用二分答案来确定答案。

那么题目就转化为了判定性问题：

• 求出每一个点以$mid$mid为最大高度，需要花费的最少积木。合法条件是存在最高点mid时使用的积木数量$\le mid$≤mid.

我们可以发现，最高点一定属于类似的金字塔。

但是金字塔一定是要完整的金字塔吗？我们可以尝试画图来理解这个问题。

• 如图所示，假设我们钦定第二列为金字塔的顶尖，那么这幅图一定是需要完整的金字塔的。
  
• 事实上，不补全金字塔，只保留金字塔的一部分也是可以的。如图所示：
  -

然后我们仔细观察图片，发现当前金子塔的节点为$i$i，高度为$x$x(二分的值)，若$j<i$j<i且同样处于金字塔内，则j的高度为$x-(i-j)$x−(i−j),若$j>i$j>i，则$j$j的高度为$x-(j-i)$x−(j−i).

那么这和我们的算法有什么关系呢？显然我们可以处理出每个顶点的左右端点。若满足条件：$x-(i-j)\le h_j$x−(i−j)≤hj​且$j$j最大,则$j$j为金字塔的左边界。若满足条件$x-(j-i)\le h_j$x−(j−i)≤hj​且$j$j最小,则$j$j是金字塔的右边界。

对于从右往左查找每一个节点的左边界，左边界一定会越来越靠左。（自行脑补）

右边界同理。那样我们就可以用两个指针来处理左右边界了。

知道左右边界$L$L和$R$R以后，我们可以得到如下结论：

• 金字塔内的节点总个数为：$x^2-\frac{L\times(L+1)}{2}-\frac{R\times(R+1)}{2}$x2−2L×(L+1)​−2R×(R+1)​
• 这个公式的依据是：
  这种形状的方块个数为:$H^2$H2
  
  这种形状的方块个数为：$\frac{H\times(H+1)}{2}$2H×(H+1)​
• 意思就是大的金字塔减去不完整情况下的两个脚。

那么我们就得到了这段区间的方块，我们就只需要看$这段区间的方块总数-(L,R)内的方块数\le m$这段区间的方块总数−(L,R)内的方块数≤m
是否成立即可。其中$(L,R)$(L,R)内的方块数用前缀和维护即可。

代码如下：

#include <cmath>
#include <cstdio>
#include <iostream>

#define int long long

using namespace std;
const int N = 2e5;

int n, m;
int h[N], L[N], R[N], s[N];

int read(void)
{
	int s = 0, w = 0; char c = getchar();
	while (c < '0' || c > '9') w |= c == '-', c = getchar();
	while (c >= '0' && c <= '9') s = s*10+c-48, c = getchar();
	return w ? -s : s;
}

bool check(int x)
{
	int l = n, r = 1;
	for (int i=n;i>=1;--i) {
		while (l >= 1 && x - (i - l) > h[l]) l --;
		L[i] = l;
	} 
	for (int i=1;i<=n;++i) {
		while (r <= n && x - (r - i) > h[r]) r ++;
		R[i] = r;
	}//查找左右边界
	for (int i=1;i<=n;++i) 
	{
		if (L[i] < 1 || R[i] > n) continue;
		int a = x - (i - L[i]), b = x - (R[i] - i);
		int need = x * x - a * (a+1) / 2 - b * (b+1) / 2;
		if (need - (s[R[i]-1] - s[L[i]]) <= m) return 1;
	}
	return 0;
}

signed main(void)
{
	freopen("block.in","r",stdin);
	freopen("block.out","w",stdout);	
	n = read(), m = read();
	for (int i=1;i<=n;++i)
	{
		h[i] = read();
		s[i] = s[i-1] + h[i];
	}
	int Left = 1, Right = 1e9;
	while (Left + 1 < Right) {
		int mid = Left + Right >> 1;
		check(mid) ? Left = mid : Right = mid;
	}
	printf("%lld", check(Right) ? Right : Left);
	return 0;
}