CF1856C To Become Max · znzryb

## 思路讲解

稍微看了眼样例，还是发现有点难度呀，这1600好像还真开始上强度了。

这狗洛谷竟然一个标签都没有，佛了。这个codeforces倒是有几个标签，什么dp，二分，什么的。但老实说我不太敢信他的tag。

哈哈，我懂了，其实是这样，正推比较难，但可以倒推（毕竟都二分答案了）。就是说这个opA[i]=x（x类似于答案，就是我假设的二分答案），那么需要多少个操作？或者永远无法达成？

## AC代码

[https://codeforces.com/problemset/submission/1856/310565408](https://codeforces.com/problemset/submission/1856/310565408)

```cpp
// Problem: CF1856C To Become Max
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1856C
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;

ll N,K,T,A[MAXN],opA[MAXN];

inline void init(){
	for(int i=1;i<=N;++i){
		opA[i]=A[i];
	}
}

inline bool check(ll x){
	for(int i=1;i<=N;++i){
		init();
		if(A[i]>=x){
			return true;
		}
		if(i==N){
			continue;
		}
		bool isAbNormal=false;
		ll opNum=0;
		opNum+=x-opA[i];
		opA[i]=x;
		for(int j=i+1;j<=N;++j){
			if(j!=N){
				if(opA[j]>=opA[j-1]-1){
					break;
				}else{
					opNum+=opA[j-1]-1-opA[j];
					opA[j]=opA[j-1]-1;
				}
			}else{
				if(opA[j]>=opA[j-1]-1){
					break;
				}				
				isAbNormal=true;
			}
		}
		
// #ifdef LOCAL
	// cerr<<x<<"\n";
	// for(int i=1;i<=N;++i){
		// cerr<<opA[i]<<" ";
	// }
	// cerr<<"\n";
	// cerr<<isAbNormal<<" "<<opNum<<"\n";
    // cerr << '\n';
// #endif
		if(!isAbNormal && opNum<=K) return true;
	}
	return false;
}

inline void solve(){
	cin>>N>>K;
	ll maxA=0;
	for(int i=1;i<=N;++i){
		cin>>A[i];
		maxA=max(A[i],maxA);
	}
	ll l=maxA,r=N+maxA+5;
	while(l<r){
		ll mid=l+r+1>>1;
		if(check(mid)){
			l=mid;
		}else{
			r=mid-1;
		}
	}
	cout<<l<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}
/*
AC
https://codeforces.com/problemset/submission/1856/310565408
*/
```

## 心路历程（WA，TLE，MLE……）