文章目录
[Plants vs. Zombies](https://zoj.pintia.cn/problem-sets/91827364500/problems/91827370312)题意解题思路代码
Plants vs. Zombies
题意
给以n个数，每个数表示浇一次水可以长高多少，你一共可以移动m次，每次移动只能移动一格，移动一次浇一次水，问你m次以后最小值最大是多少
解题思路
这个题刚开始看到没一点思路，仔细一想就是二分了，我们二分最小值最大是多少，每次check的时候当这个位置没有check值大，我们就浇这个，并且向后移动再回来，这样一直check下去，如果最后步数不够用就说明check值太大了。 有个细节就是最后一步要特判，因为有可能给倒数第二个位置浇水的时候顺便给他浇的满足情况了；
代码
#include<bits/stdc++.h>
using namespace std
;
#define ll long long
const ll mod
=1000000007;
const int mx
=100100;
ll n
,m
;
ll a
[mx
];
bool
check(ll x
){
ll tem
=m
;
ll y
=0,cnt
;
ll res
;
for(int i
=1;i
<n
;i
++){
cnt
=a
[i
]*(y
+1);
tem
--;
if(cnt
<x
){
res
=x
-cnt
;
y
=(res
+a
[i
]-1)/a
[i
];
tem
=tem
-y
*2LL;
if(tem
<0) return 0;
}
else{
y
=0;
}
}
if(a
[n
]*y
<x
){
tem
--;
res
=x
-(a
[n
]*y
+a
[n
]);
y
=(res
+a
[n
]-1)/a
[n
];
tem
-=y
*2;
}
return tem
>=0;
}
int main(){
ios
::sync_with_stdio(0);
int _
;
cin
>>_
;
while(_
--){
cin
>>n
>>m
;
ll ma
=0;
for(int i
=1;i
<=n
;i
++){
cin
>>a
[i
];
ma
=max(ma
,a
[i
]);
}
if(m
<n
) {
cout
<<"0\n";
continue;
}
ll l
=0LL,r
=m
*ma
+7;
ll mid
,ans
=0;
while(l
<=r
){
mid
=(l
+r
)/(ll
)2;
if(check(mid
)){
ans
=mid
;
l
=mid
+1LL;
}else{
r
=mid
-1LL;
}
}
cout
<<ans
<<"\n";
}
return 0;
}
