题目链接:Plants vs. Zombies
题意:从1到n每个位置一棵植物,植物每浇水一次,增加ai高度。人的初始位置为0,人每次能往左或往右走一步,走到哪个位置就浇水一次。求m步走完后最低高度的植物最大高度为多少。
题解:明显二分答案的题目。check时从左往右遍历,贪心思路:把该位置满足同时给后面减少浇水次数,策略是该位置和后一个位置左右横跳,注意最后一个位置的时候,如果满足就不需要再跳过去。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N=1e5+;
typedef long long ll;
ll a[N],d[N],n,m; bool check(ll k){
for(ll i=;i<=n;i++) d[i]=;
ll cnt=m;
for(ll i=;i<=n;i++){
if(cnt==){
if(i==n&&d[i]>=k) return true;
return false;
}
cnt--;
d[i]+=a[i];
if(d[i]<k){
ll tmp=k-d[i];
ll c=tmp/a[i];
if(tmp%a[i]!=) c++;
if(cnt>=*c){
cnt-=*c;
d[i]+=(a[i]*c);
d[i+]+=(a[i+])*c;
}
else return false;
}
}
return true;
} int main(){
int t;
scanf("%d",&t); while(t--){
ll ans=;
scanf("%lld%lld",&n,&m);
for(ll i=;i<=n;i++){
scanf("%lld",&a[i]);
}
ll l=,r=1e17+;
while(l<=r){
ll mid=(l+r)/;
if(check(mid)) ans=max(ans,mid),l=mid+;
else r=mid-;
}
printf("%lld\n",ans);
} return ;
}