植物大戰殭屍為近來很火的一款遊戲。而這一次我們不一樣，我們要提前養成植物然後來抵抗殭屍。
你的 nn 個植物已經從左到右排成了一排，編號從 11 到 nn，起始的時候，他們的防禦都是 00，而你的任務就是來提高他們的防禦。
你一共有 mm 天的時間進行備戰，起始你在整個植物的最左邊，每天你 必須 向左或向右移動一格，到達第 ii 棵植物的時候，你給這個植物增加 a_iai 點的防禦。
眾所周知，根據木桶原理，整排植物的防禦取決於最低防禦的一棵植物，你想讓 mm 天以後的整排植物的防禦力最高，請問最高能是多少呢？
輸入資料第一行包含以空格隔開的兩個整數 n,mn,m，分別表示植物總數和你的備戰天數。
第二行包含以空格隔開的 nn 個整數 a_1.a_2,\cdots,a_na1.a2,⋯,an，表示每次一個植物可以增加的防禦力。
輸出檔案共一行包括一個整數，表示整排植物可以達到的最大防禦力。
| # | nn | mm | a_iai |
|---|---|---|---|
| 1\sim31∼3 | 2\leq n \leq 102≤n≤10 | 0 \leq m \leq 200≤m≤20 | 1\leq a_i \leq 10^51≤ai≤105 |
| 4\sim64∼6 | 2 \leq n \leq 1002≤n≤100 | 0 \leq m \leq 1,0000≤m≤1,000 | 1\leq a_i \leq 10^51≤ai≤105 |
| 7\sim107∼10 | 2 \leq n \leq 10^52≤n≤105 | 0 \leq m \leq 10^{12}0≤m≤1012 | 1\leq a_i \leq 10^51≤ai≤105 |
樣例輸入複製
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;
}