Gym - 100851L [二分+线性推导]

题目链接:https://vjudge.net/problem/Gym-100851L

解题思路:

根据题目知道，墙的两边是不能放石头的，所以最终的结果肯定会收到两边墙的限制，从而使得答案不会超过1e9+1e5。

此外我们再去二分最大高度，一个明显的结论就是以i为最高点建墙的话最少花费肯定是建一个金字塔形的墙面。但由于原始的墙面，有可能花费的更少，也就是当某一竖墙在金字塔的位置的高度小于等于原始该竖墙的高度时，相当于金字塔被隔断了，不用再考虑往下面建上来了，所以我们就要去找到以i为金字塔顶端，它的左右隔断位置，显然这是一个线性单调的结果，所以只要从后往前和从前往后扫一遍就可以找到了。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int mx = 1e5+10;
int n,K,L[mx],R[mx];
ll m,a[mx],pre[mx];
ll cal(ll x,ll d){
	return x*d + d*(d-1)/2;
}	
bool check(ll x){
	int r = n,l = 1;
	for(int i=r-1;i>=0&&r>=1;i--){
		while(i<r&&r>=x+i-a[i])
		L[r--] = i;
	}
	for(int i=l+1;i<=n+1&&l<=n;i++){
		while(i>l&&l<=a[i]+i-x)
		R[l++] = i;
	}
	for(int i=1;i<=n;i++){
		if(a[i]>=x) return 1;
		int l = i - L[i],r = R[i] - i;
		if(L[i]==0||R[i]==n+1) continue;
		ll sum = pre[i+r-1] - pre[i-l];
		ll ret = cal(x-l+1,l) - x + cal(x-r+1,r);
		if(ret<=sum+m) return 1;
	}
	return 0;
}
int main(){
	freopen("landscape.in","r",stdin);
	freopen("landscape.out","w",stdout);
	scanf("%d%lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",a+i);
		pre[i] = pre[i-1] + a[i];
	}
	a[0] = a[n+1] = 2e9;
	ll l = 1,r = 2e9;
	while(l<r){
		ll mid = (l+r+1)>>1;
		if(check(mid)) l = mid;
		else r = mid - 1;
	}
	printf("%lld\n",l);
	return 0;
}