- 1000ms
- 262144K
植物大戰僵尸為近來很火的一款游戲，而這一次我們不一樣，我們要提前養成植物然后來抵抗僵尸，
你的 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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/159992.html
標籤：其他
上一篇：2020電賽準備總結（三）
下一篇：「總結」樹形DP