思路:
题目谈到最小值最大值或者需要枚举时,可以想下能否用二分来做
1.满足二段性
2.具有单调性(有单调一定可以二分,没有看情况)
private static int n;
private static int maxH;//存储数组中最大的数
private static int[] H=new int[100010];
public static boolean check(int x) {
for(int i=0;i<n;i++) {
if(x>=maxH)return true;//若x比他大,那么后面就会一直累加,不判断的话就会数据溢出
x=2*x-H[i];
if(x<0)return false;
}
return true;
}
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
n=scanner.nextInt();
for(int i=0;i<n;i++) {
H[i]=scanner.nextInt();
maxH=Math.max(H[i], maxH);
}
int l=0,r=100000;
while(l<r) {
int mid=l+r>>1;
if(check(mid))r=mid;
else l=mid+1;
}
System.out.println(l);
}
dk