Codeforces Codeforces Round 890 (Div. 2) C. To Become Max
原题链接
中等
作者:
风轻云淡墨
,
2023-08-06 19:17:04
,
所有人可见
,
阅读 74
//二分答案
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,k;LL p[1001],a[1001];
bool check(int x,int v)
{
for(int i=1;i<=n;i++)p[i]=a[i];
LL val=v-p[x];//将当前位置变成猜测值的次数
p[x]=v;//更新
if(val>k)return 0;
for(int i=x+1;i<=n;i++)
{
if(p[i]+1>=p[i-1])return 1;//4 3只要3+1>=4,3就可以把前一个数变成4
else val+=p[i-1]-p[i]-1,p[i]=p[i-1]-1;//后一个比前一个少1就行
if(val>k)return 0;
}
return 0;
}
void sovle()
{
cin>>n>>k; LL ans=0;
for(int i=1;i<=n;i++)cin>>a[i],ans=max(ans,a[i]);
// ans=a[n];//1
// 5 1
// 6 3 2 1 5//这样原本的6按步骤不能推到。这种本来位置值不变的本来后面就不用变,直接初始化。
for(int i=1;i<=n;i++)//枚举每一个点
{
int l=0,r=1e9;
while(l<=r)//如果是l<r,那r==l,mid==r===l的情况会漏一个
{
LL mid=(l+r)>>1;//二分答案
if(check(i,mid))l=mid+1,ans=max(ans,mid);//如果可以达到,答案往大的接着找
else r=mid-1;
}
}
cout<<ans<<endl;
}
int main()
{
int q;cin>>q;while(q--)sovle();
}