大家好，又见面了，我是全栈君。
二分枚举长度改变的长度即可了
#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;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/116609.html原文链接：https://javaforall.net
