植物大战僵尸为近来很火的一款游戏。而这一次我们不一样，我们要提前养成植物然后来抵抗僵尸。
你的 nn 个植物已经从左到右排成了一排，编号从 11 到 nn，起始的时候，他们的防御都是 00，而你的任务就是来提高他们的防御。
你一共有 mm 天的时间进行备战，起始你在整个植物的最左边，每天你 必须 向左或向右移动一格，到达第 ii 棵植物的时候，你给这个植物增加 a_iai 点的防御。
众所周知，根据木桶原理，整排植物的防御取决于最低防御的一棵植物，你想让 mm 天以后的整排植物的防御力最高，请问最高能是多少呢？
输入数据第一行包含以空格隔开的两个整数 n,mn,m，分别表示植物总数和你的备战天数。
第二行包含以空格隔开的 nn 个整数 a_1.a_2,\cdots,a_na1.a2,⋯,an，表示每次一个植物可以增加的防御力。
输出文件共一行包括一个整数，表示整排植物可以达到的最大防御力。
样例输入复制
4 8 3 2 6 6样例输出复制
6 #include<cstdio> using namespace std; const int N = 1e5 + 10; typedef long long ll; ll n,m; ll num[N]; bool check(ll x)//判断当前防御力在m天内是否可行 { ll last=0, now=0;//左右横跳对上一位置进行更改时，对当前位置造成的影响 ll sum = 0; for(int i=0; i<n; i++) { now = x/num[i] + (x%num[i] ? 1 : 0);//达到x值所需天数 now -= last; if(now > 0)//需要继续更改，则会对下一位置照成影响 { last = now - 1; } else { if(i == n-1) //到最后一个位置不需要继续移动 { now = 0; last = 0; } else { now = 1;//移动需要一天 last = 0; } } sum += now + last; if(sum > m) return 0; } return 1; } int main() { scanf("%lld%lld",&n,&m); for(int i=0; i<n; i++) scanf("%lld", &num[i]); ll l = 1, r = 1e18; ll mid; while(l < r)//二分寻找最大防御力 { mid = (l + r) >> 1; if(check(mid)) l = mid+1; else r = mid; } printf("%lld", l-1); return 0; }
