题意
原题面一堆废话,其实这道题很简单。
\(T\) 组数据,每组数据给定你一个长度为 \(n\) 的序列 \(a_1...a_n\),在定义 \(a_0\) 为 \(0\) 的情况下,假设 \(k\) 为你的力量系数,在 \(\forall i \in n\) 时 \(a_i-a_{i-1} \le k\),且在按顺序 \(1-n\) 进行判断时,如果 \(a_i-a_{i-1} = k\) 那么 \(k=k-1\),\(k\) 会对后面造成影响。求 \(k\) 的最小值。
思路
二分 \(k\) 的值,按照题意模拟即可。
代码
#include<bits/stdc++.h>
#define N 1000005
using namespace std;
int n,m,a[N],idx;
bool check(int x){
for(int i=1;i<=n;i++){
if(a[i]-a[i-1]>x) return 0;//不符合条件
if(a[i]-a[i-1]==x) x--;//k--
}
return 1;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
int T;
cin>>T;
while(T--){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int l=0,r=10000000;
while(r-l>5){
int mid=l+r>>1;
if(check(mid)){
r=mid;
}
else{
l=mid;
}
}
int ans=1e9;
for(int i=l;i<=r;i++){
if(check(i)){
ans=min(ans,i);//二分k的最小值
}
}
cout<<"Case "<<++idx<<": "<<ans<<endl;//输出答案即可,注意格式
}
}
标签:题意,int,题解,mid,cin,--,UVA12032
From: https://www.cnblogs.com/Telsif/p/18002029