八月Day9

T3

推一下样例，会发现最后改变的那个区间一定是不递减的。

可以二分答案。

check函数( bool check(int x) )：

    枚举每个点i作为区间起点（也就是作为答案）

    向右枚举区间中的每一个点。

    设剩余增加次数为now，初始化为k.

    设对于要填的点j,目前的目标增加量设为go.

    go = x - ( j - i )

    如果a[j]>=go. 那么now >= 0, 则true.

    如果已经枚举到了第n个，此时没有跳出循环说明

        若

            a[n] >= go 且 now >= 0，则true.

        若

            a[n] < go, 则 break

    每次循环之时now -= a[j] - go.

    最后函数末尾放一个return false.

    注意二分上界，设大一点。

    时间复杂度:O(n^2 * 30)

#include<bits/stdc++.h>
using namespace std;
int T;
long long n,k;
long long a[1005];
bool check(long long x) {
	for(int i = 1;i <= n;i ++) {
		long long now = k;
		for(int j = i;j <= n;j ++) {
			if(j == n && a[n] < x - (j - i)) {
				now = -1;
				break;
			}
			if(x - (j - i)   <=  a[j]) break;
			now -= x - (j - i) - a[j];
            if(now < 0) break;
		}
		if(now >= 0) return true;
	}
	return false;
}
void solve() {
	cin >> n >> k;
	for(int i = 1;i <= n;i ++) cin >> a[i];
	int l = 1,r = 200000001;
	while(l < r) {
		int mid = (l+r+1) / 2;
		if(check(mid)) l = mid;
		else r = mid - 1;
	}
	cout << l << "\n";
	return;
}
int main() {
	cin >> T;
	while(T --)	solve();
	return 0;
}