题意：有n个植物排成一排，标号为1-n，每株植物有自己的生长速度ai，每对植物浇一次水，该株植物就长高ai，
现在机器人从第0个格子出发，每次走一步，不能停留，每一步浇一次水，总共可以走m步，问最矮的植物最高是多少。
n<=1e6，sigma n<=1e7，0<=m<=1e12，1<=a[i]<=1e5
思路：7Y……你不死谁死
显然最小值最大可以二分，二分答案，最优的策略一定是从左到右依次左右横跳，直到当前格子不小于二分的值
一个致命的细节：最后一个如果在倒数第二个左右横跳的时候已经够了则不需要再走到了
1 #include<cstdio> 2 #include<cstring> 3 #include<string> 4 #include<cmath> 5 #include<iostream> 6 #include<algorithm> 7 #include<map> 8 #include<set> 9 #include<queue> 10 #include<vector> 11 using namespace std; 12 typedef long long ll; 13 typedef unsigned int uint; 14 typedef unsigned long long ull; 15 typedef pair<int,int> PII; 16 typedef vector<int> VI; 17 #define fi first 18 #define se second 19 #define MP make_pair 20 #define N 110000 21 #define M 51 22 #define MOD 1000000007 23 #define eps 1e-8 24 #define pi acos(-1) 25 #define oo 1010000000 26 27 ll a[N],b[N],m; 28 int n; 29 30 int isok(ll k) 31 { 32 for(int i=1;i<=n+1;i++) b[i]=0; 33 ll t=0; 34 for(int i=1;i<=n;i++) 35 { 36 if(i==n&&b[n]>=k) continue; 37 t++; 38 if(t>m) return 0; 39 b[i]+=a[i]; 40 if(b[i]<k) 41 { 42 ll tmp=(k-b[i])/a[i]; 43 if(tmp*a[i]+b[i]<k) tmp++; 44 t=t+tmp*2; 45 if(t>m) return 0; 46 b[i]+=a[i]*tmp; 47 b[i+1]+=a[i+1]*tmp; 48 } 49 } 50 if(t>m) return 0; 51 return 1; 52 } 53 54 int main() 55 { 56 int cas; 57 scanf("%d",&cas); 58 for(int v=1;v<=cas;v++) 59 { 60 scanf("%d%lld",&n,&m); 61 for(int i=1;i<=n;i++) scanf("%lld",&a[i]); 62 ll l=1; 63 ll r=1e17; 64 ll last=0; 65 while(l<=r) 66 { 67 ll mid=(l+r)/2; 68 if(isok(mid)){last=mid; l=mid+1;} 69 else r=mid-1; 70 } 71 printf("%lld ",last); 72 } 73 return 0; 74 } 75