大家好,又见面了,我是全栈君。
二分枚举长度改变的长度即可了
#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; }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116609.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...