二分枚举长度改变的长度即可了
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF = 3000000;
const int maxn = 100005;
int n,arr[maxn],arr2[maxn];
bool solve(int x){
memcpy(arr2,arr,sizeof(arr));
for(int i = 1; i <= n; i++){
if(arr2[i] > arr2[i - 1]){
arr2[i] = max(arr2[i - 1] + 1,arr2[i] - x);
}
else{
if(arr2[i] + x <= arr2[i - 1]) return false;
arr2[i] = arr2[i - 1] + 1;
}
}
return true;
}
int main(){
int T,Case = 1;
scanf("%d",&T);
arr[0] = -INF;
while(T--){
scanf("%d",&n);
for(int i = 1; i <= n; i++)
scanf("%d",&arr[i]);
int l = 0,r = INF;
int ans = n;
while(l <= r){
int mid = (l + r) >> 1;
if(solve(mid)){
ans = mid;
r = mid - 1;
}
else
l = mid + 1;
}
printf("Case #%d:\n",Case++);
printf("%d\n",ans);
}
return 0;
}