Problem L. Landscape Improved
Input file: landscape.in
Output file: landscape.out
Louis L Le Roi-Univers has ordered to improve the landscape that is seen from the royal palace. His
Majesty prefers to see a high mountain.
The Chief Landscape Manager is going to raise a mountain for Louis. He represents a landscape as a
flat picture on a grid of unit squares. Some of the squares are already filled with rock, while others are
empty. This greatly simplifies the design. Unit squares are small enough, and the landscape seems to be
smooth from the royal palace.
The Chief Landscape Manager has a plan of the landscape — the heights of all rock-filled columns for
each unit of width. He is going to add at most n square units of stones atop of the existing landscape to
make a mountain with as high peak as possible. Unfortunately, piles of stones are quite unstable. A unit
square of stones may be placed only exactly on top of the other filled square of stones or rock, moreover
the squares immediately to the bottom-left and to bottom-right of it should be already filled.
Existing landscape
Improved landscape
Your task is to help The Chief Landscape Manager to determine the maximum height of the highest
mountain he can build.
Input
The first line of the input file contains two integers w — the width of the existing landscape and n —
the maximum number of squares of stones to add (1 ≤ w ≤ 100 000, 0 ≤ n ≤ 1018).
Each of the following w lines contains a single integer hi — the height of the existing landscape column
(1 ≤ hi ≤ 109
).
Output
The output file shall contain the single integer — the maximum possible landscape height after at most
n unit squares of stones are added in a stable way.
Sample input and output
landscape.in landscape.out
8 4
3
4
2
1
3
3
2
4
5
3 100
3
3
3
题意：这题是给你w列方格，然后给你n个方块，让你加进去，使得这个图变得最高，加的要求是，如果这块的下面，以及左下右下都有，才能放
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
#include <queue>
#include <vector>
#define MM(a,b) memset(a,b,sizeof(a));
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
#define CT continue
#define SC scanf
const int N=1e5+10;
int h[N],l[N],r[N];
ll sum[N];
int n; ll w;
bool ok(int mid)
{
MM(r,inf);MM(l,0);
for(int i=1;i<=n;i++) {
ll a=i-(mid-h[i]),
b=i+(mid-h[i]);
if(a>=1) r[a]=min(r[a],i);
if(b<=n) l[b]=max(l[b],i);
}
for(int i=1;i<=n;i++) l[i]=max(l[i],l[i-1]);
for(int i=n;i>=1;i--) r[i]=min(r[i],r[i+1]);
for(int i=1;i<=n;i++) {
if(l[i]==0||r[i]==inf) CT;
ll all=0;
int k1=i-(l[i]+1)+1;
all+=((ll)k1)*mid-((ll)k1)*(k1-1)/2LL;
int k2=(r[i]-1)-i+1;
all+=((ll)k2)*mid-((ll)k2)*(k2-1)/2LL;
all-=mid;
if(all-(sum[r[i]-1]-sum[l[i]])<=w) return true;
}
return false;
}
int main()
{
freopen("landscape.in","r",stdin);
freopen("landscape.out","w",stdout);
while(~SC("%d%lld",&n,&w))
{
int maxn=0;
MM(sum,0);
for(int i=1;i<=n;i++) {
SC("%d",&h[i]);
maxn=max(maxn,h[i]);
sum[i]=sum[i-1]+h[i];
}
int la=maxn,ra=2*1e9;
while(ra-la>1){
int mid=(la+(ll)ra)>>1;
if(ok(mid)) la=mid;
else ra=mid;
}
printf("%d
",la);
}
return 0;
}