題目描述

在運動會上，小明從數軸的原點開始向正方向立定跳遠。項目設置了 $n$ 個檢查點 $a_1,a_2,?,a_n$ 且 $a_i\ge a_{i?1}>0$。小明必須先后跳躍到每個檢查點上且只能跳躍到檢查點上。同時，小明可以自行再增加 $m$ 個檢查點讓自己跳得更輕松。

在運動會前，小明制定訓練計劃讓自己單次跳躍的最遠距離達到 $L$，并且學會一個爆發技能可以在運動會時使用一次，使用時可以在該次跳躍時的最遠距離變為 $2L$。小明想知道，$L$ 的最小值是多少可以完成這個項目？

輸入格式

輸入共 $2$ 行。

第一行為兩個正整數 $n,m$。

第二行為 $n$ 個由空格分開的正整數 $a_1,a_2,?,a_n$。

輸出格式

輸出共 $1$ 行，一個整數表示答案。

輸入輸出樣例 #1

輸入 #1

5 3
1 3 5 16 21

輸出 #1

3

說明/提示

【樣例說明】

增加檢查點 $10,13,19$，因此每次跳躍距離為 $1,2,2,5,3,3,3,2$，在第三次跳躍時使用技能即可。

【評測用例規模與約定】

對于 $20\%$ 的評測用例，保證 $n\le 10^2$，$m\le 10^3$，$a_i\le 10^3$。
對于 $100\%$ 的評測用例，保證 $2\le n\le 10^5$，$m\le 10^8$，$0<a_i\le 10^8$。

解題核心思路是通過二分查找來確定小明單次跳躍的最小距離 L，同時考慮到他可以使用一次爆發技能將某一次跳躍距離變為 2L
對于每個候選的 L（即 mid），計算在不使用技能的情況下，需要添加多少個新檢查點才能使所有跳躍距離不超過 L。
具體計算方法：對于每兩個相鄰的原檢查點 a[i-1] 和 a[i]，所需的新檢查點數為 ceil((a[i] - a[i-1]) / mid) - 1。
如果總添加的檢查點數不超過 m + 1，則說明當前 L 可能是可行的（因為可以用一次技能覆蓋一個較長的跳躍）。
關鍵邏輯：通過允許添加 m + 1 個檢查點（而不是 m 個），我們隱式地利用了一次技能的機會，因為技能可以將一次跳躍距離翻倍，相當于減少了一個需要添加檢查點的間隔。

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005],ans;bool check(int mid){int cnt=0;for(int i=1;i<=n;++i){cnt+=(int)ceil((a[i]-a[i-1])*1.0/mid)-1;}return cnt<=m+1;
}int main(){cin>>n>>m;for(int i=1;i<=n;++i)cin>>a[i];int l=1,r=a[n];while(l<r){int mid=l+r>> 1;if(check(mid))r=mid;else l=mid+1;}cout<<l;return 0;
}