关于这场div2，只能说一言难尽
C题可以二分的，赛时看到n<=1000,直接往\(O(n^2)\)考虑 ，想了一会贪心的话能写出来，但是，细节太多没调出来，G掉打分。
\(O(n^2)\)做法：
思路：每次让i为起点，往前贪心枚举，并且当前位置如果满足，也要枚举当前区间，细节就是要注意上下限，赛时，漏了一种上界小于下届的情况，所以一直wa。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7;
int mod=1e9+7;
int a[N];
int n,k;
void solve()
{
cin>>n>>k;
int x;
int ans=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
ans=max(ans,a[i]);
}
a[n+1]=a[n]-1; //这里多加个，让最后两位也计算
n++;
for(int i=2;i<n;i++)
{
int x=a[i],xx=a[i+1]+1; //起点的下上限
xx=max(xx,x); //注意这里要保证xx>=x
int w=a[i]; //表示上一位的值
int sss=a[i]; //j+1 位置的值
int p=0; //j+1位置达到sss所花费的值
for(int j=i-1;j>=1;j--) //二层循环，每次只看当前位置
{
w=max(w+1,a[j]+1);//当前位置的最大值
if(w-(i-j)<=xx) //如果最值大于上限，break
{
int cc=p+w-a[j]+(i-j)*(w-1-sss); //当前位置达到最值的花费，
sss=w; //记录当前位置，最值，方便下次用
p=cc; //记录当前花费，方便下次累加
if(cc<=k)//当前位置达到最值时，花费是否满足
{
ans=max(ans,w); //更新答案
int kk=k-cc;
ans=max(ans,min(xx+i-j,w+kk/(i-j+1))); //剩余操作次数，对区间整体操作，注意小于上界
}
else break;
}
else break;
}
}
cout<<ans<<'\n';
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t=1;
cin>>t;
while(t--)
{
solve();
}
return 0;
}
二分做法时间复杂度大概\(O(n^2log(MAX))\)，就不多说了，
标签：890,supported,Institute,Max,位置,Codeforces,int,ans,Become From： https://www.cnblogs.com/xxj112/p/17609408.html