問題描述

在運動會上，小明從數軸的原點開始向正方向立定跳遠。項目設置了?n?個檢查點?a1,a2,...,an且?ai≥ai?1>0。小明必須先后跳躍到每個檢查點上且只能跳躍到檢查點上。同時，小明可以自行再增加?m?個檢查點讓自己跳得更輕松。在運動會前，小明制定訓練計劃讓自己單次跳躍的最遠距離達到?L，并且學會一個爆發技能可以在運動會時使用一次，使用時可以在該次跳躍時的最遠距離變為?2L。小明想知道，L?的最小值是多少可以完成這個項目？

輸入格式

輸入共?2?行。第一行為兩個正整數?n,m。第二行為?nn個由空格分開的正整數?a1,a2,...,an?。

輸出格式

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

樣例輸入

5 3
1 3 5 16 21

樣例輸出

3

樣例說明

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

評測用例規模與約定

對于?20% 的評測用例，保證?n≤10^2,m≤10^3,ai≤10^3。 對于?100%的評測用例，保證?2≤n≤10^5,m≤10^8,0<ai≤10^8。

解題思路：

從原點開始起跳到第一個檢查點，這段距離別忘；一次爆發可看做多給一次檢查點（因為爆發能跳2L，就相當于在2L中間插個檢查點，分成了兩段L）。

用二分來查找最小的能滿足給定m+1（+1為一次爆發）的L（即mid）。

怎么判斷是否滿足m+1：

①先求出在選定的mid的情況下，完成項目所需的檢查點數requireM。

②再判斷所需的檢查點數requireM是否滿足<=m+1

③若滿足，再使right=mid-1，減小mid，看能否取更小

④若不滿足，則使left=mid+1，增大mid，使滿足

⑤直到找到最小的mid (即L)

計算完成項目所需的檢查點數requireM：

通過計算每兩個相鄰檢查點之間的距離d可以劃分為多少段長度為L的段落（向上取整），即（d+mid-1）/mid（在數學中與ceil( d/mid )等價）， 這兩個檢查點間所需的檢查點數即為段落數-1即可，為（d+mid-1）/mid-1，即（d-1）/mid。

代碼：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc=new Scanner(System.in);int n=sc.nextInt();int m=sc.nextInt()+1;//爆發可以看作多給一個檢查點int[] a=new int[n];for(int i=0;i<n;i++) {a[i]=sc.nextInt();}int[] distance=new int[n];distance[0]=a[0];//注意！！！從原點開始跳到第一個檢查點的距離for(int i=0;i<n-1;i++) {distance[i+1]=a[i+1]-a[i];}int left=1;int right=(int)1e8;int answer=0;while(left<=right) {int mid=left+(right-left)/2;long requireM=0;for(int d:distance) {requireM+=(d-1)/mid;//d/mid的向上取整再-1，d/mid表示距離d能劃分為多少段長度為mid段落，再-1即為需增加的檢查點}if(requireM<=m) {answer=mid;right=mid-1;}else {left=mid+1;}}System.out.println(answer);sc.close();}}