2023-08-06：小青蛙住在一條河邊, 它想到河對(duì)岸的學(xué)校去學(xué)習(xí) 小青蛙打算經(jīng)過(guò)河里 的石
2023-08-06：小青蛙住在一條河邊, 它想到河對(duì)岸的學(xué)校去學(xué)習(xí)
小青蛙打算經(jīng)過(guò)河里 的石頭跳到對(duì)岸
河里的石頭排成了一條直線, 小青蛙每次跳躍必須落在一塊石頭或者岸上
給定一個(gè)長(zhǎng)度為n的數(shù)組arr，表示每塊兒石頭的高度數(shù)值
每塊石頭有一個(gè)高度, 每次小青蛙從一塊石頭起跳
這塊石頭的高度就會(huì)下降1, 當(dāng)石頭的高度下降到0時(shí)
小青蛙不能再跳到這塊石頭上(跳躍后使石頭高度下降到0是允許的)
小青蛙一共需要去學(xué)校上x(chóng)天課, 所以它需要往返x次(去x次，回x次)
當(dāng)小青蛙具有 一個(gè)跳躍能力y時(shí), 它能跳不超過(guò)y的距離。
請(qǐng)問(wèn)小青蛙的跳躍能力至少是多少才能用這些石頭上完x次課？
1 <= n <= 10^5，
1 <= arr[i] <= 10^4，
1 <= x <= 10^9。
來(lái)自藍(lán)橋杯練習(xí)題。
來(lái)自左神
答案2023-08-06：
#大體步驟如下：
1.讀取輸入：從輸入中讀取每塊石頭的高度數(shù)值和小青蛙需要上課的天數(shù)x。
2.初始化變量和數(shù)組：定義一個(gè)長(zhǎng)度為n的數(shù)組help用于保存每塊石頭的高度數(shù)值的累積和。初始化變量ans為0。
3.計(jì)算累積和：遍歷數(shù)組arr中的每個(gè)元素，計(jì)算它們的累積和，并保存到數(shù)組help中。
4.計(jì)算最小跳躍能力：使用雙指針?lè)ㄖ饌€(gè)計(jì)算每個(gè)起點(diǎn)石頭l到終點(diǎn)石頭r的跳躍能力。在每次迭代中，通過(guò)移動(dòng)r指針使得help[r] - help[l-1] >= 2*x，即小青蛙能從起點(diǎn)石頭跳躍到終點(diǎn)石頭。同時(shí)，更新ans為當(dāng)前最大的能連續(xù)跳躍的石頭數(shù)量。
5.返回結(jié)果：返回ans作為小青蛙的最小跳躍能力。
總的時(shí)間復(fù)雜度為O(n)，總的空間復(fù)雜度為O(n)。
go完整代碼如下：
package?main
import?(
????"fmt"
)
const?MAXN?=?100001
var?help?[MAXN]int
var?n,?x?int
var?sc?=?[]int{5,?1,?1,?0,?1,?0}
var?ii?=?0
func?next()?int?{
????ii++
????return?sc[ii-1]
}
func?hasNext()?bool?{
????return?ii?<?len(sc)
}
func?main()?{
????for?hasNext()?{
????????n?=?next()
????????x?=?next()
????????for?i?:=?1;?i?<?n;?i++?{
????????????val?:=?next()
????????????help[i]?=?help[i-1]?+?val
????????}
????????fmt.Println(minAbility())
????}
}
//?O(N)的最優(yōu)解
func?minAbility()?int?{
????ans?:=?0
????for?l,?r?:=?1,?1;?l?<?n;?l++?{
????????for?r?<?n?&&?help[r]-help[l-1]?<?2*x?{
????????????r++
????????}
????????ans?=?max(ans,?r-l+1)
????}
????return?ans
}
func?max(a,?b?int)?int?{
????if?a?>?b?{
????????return?a
????}
????return?b
}
rust完整代碼如下：
const?MAXN:?usize?=?100001;
static?mut?HELP:?[i64;?MAXN]?=?[0;?MAXN];
static?mut?N:?i64?=?0;
static?mut?X:?i64?=?0;
static?mut?SC:?[i64;?6]?=?[5,?1,?1,?0,?1,?0];
static?mut?II:?usize?=?0;
fn?next()?->?i64?{
????unsafe?{
????????II?+=?1;
????????SC[II?-?1]
????}
}
fn?has_next()?->?bool?{
????unsafe?{?II?<?SC.len()?}
}
fn?main()?{
????unsafe?{
????????while?has_next()?{
????????????N?=?next();
????????????X?=?next();
????????????for?i?in?1..N?{
????????????????let?val?=?next();
????????????????HELP[i?as?usize]?=?HELP[i?as?usize?-?1]?+?val;
????????????}
????????????println!("{}",?min_ability());
????????}
????}
}
//?O(N)的最優(yōu)解
fn?min_ability()?->?i64?{
????let?mut?ans:?i64?=?0;
????unsafe?{
????????let?mut?l:?i64?=?1;
????????let?mut?r:?i64?=?1;
????????while?l?<?N?{
????????????while?r?<?N?&&?HELP[r?as?usize]?-?HELP[(l?-?1)?as?usize]?<?2?*?X?{
????????????????r?+=?1;
????????????}
????????????ans?=?max(ans,?r?-?l?+?1);
????????????l?+=?1;
????????}
????}
????ans
}
fn?max(a:?i64,?b:?i64)?->?i64?{
????if?a?>?b?{
????????a
????}?else?{
????????b
????}
}
c++完整代碼如下：
int?help[MAXN];
int?n,?x;
int?sc[]?=?{?5,?1,?1,?0,?1,?0?};
int?ii?=?0;
int?next()?{
????ii++;
????return?sc[ii?-?1];
}
int?hasNext()?{
????return?ii?<?sizeof(sc)?/?sizeof(sc[0]);
}
int?min(int?a,?int?b)?{
????return?(a?<?b)???a?:?b;
}
int?max(int?a,?int?b)?{
????return?(a?>?b)???a?:?b;
}
int?minAbility()?{
????int?ans?=?0;
????for?(int?l?=?1,?r?=?1;?l?<?n;?l++)?{
????????while?(r?<?n?&&?help[r]?-?help[l?-?1]?<?2?*?x)?{
????????????r++;
????????}
????????ans?=?max(ans,?r?-?l?+?1);
????}
????return?ans;
}
int?main()?{
????while?(hasNext())?{
????????n?=?next();
????????x?=?next();
????????for?(int?i?=?1;?i?<?n;?i++)?{
????????????int?val?=?next();
????????????help[i]?=?help[i?-?1]?+?val;
????????}
????????printf("%d\n",?minAbility());
????}
????return?0;
}
c完整代碼如下：
int?help[MAXN];
int?n,?x;
int?sc[]?=?{?5,?1,?1,?0,?1,?0?};
int?ii?=?0;
int?next()?{
????ii++;
????return?sc[ii?-?1];
}
int?hasNext()?{
????return?ii?<?sizeof(sc)?/?sizeof(sc[0]);
}
int?min(int?a,?int?b)?{
????return?(a?<?b)???a?:?b;
}
int?max(int?a,?int?b)?{
????return?(a?>?b)???a?:?b;
}
int?minAbility()?{
????int?ans?=?0;
????for?(int?l?=?1,?r?=?1;?l?<?n;?l++)?{
????????while?(r?<?n?&&?help[r]?-?help[l?-?1]?<?2?*?x)?{
????????????r++;
????????}
????????ans?=?max(ans,?r?-?l?+?1);
????}
????return?ans;
}
int?main()?{
????while?(hasNext())?{
????????n?=?next();
????????x?=?next();
????????for?(int?i?=?1;?i?<?n;?i++)?{
????????????int?val?=?next();
????????????help[i]?=?help[i?-?1]?+?val;
????????}
????????printf("%d\n",?minAbility());
????}
????return?0;
}
