CF1856C To Become Max 题解 贪心

To Become Max

传送门

You are given an array of integers $a$ of length $n$.

In one operation you:

• Choose an index $i$ such that $1\le i\le n?1$ and $a_i\le a_{i+1}$.
• Increase $a_i$ by $1$.

Find the maximum possible value of $\max (a_1,a_2,\dots a_n)$ that you can get after performing this operation at most $k$ times.

Input

Each test contains multiple test cases. The first line of input contains a single integer $t$ ($1\le t\le 100$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($2\le n\le 1000$, $1\le k\le 10^8$) — the length of the array $a$ and the maximum number of operations that can be performed.

The second line of each test case contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^8$) — the elements of the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$.

Output

For each test case output a single integer — the maximum possible maximum of the array after performing at most $k$ operations.

Example

input

6
3 4
1 3 3
5 6
1 3 4 5 1
4 13
1 1 3 179
5 3
4 3 2 2 2
5 6
6 5 4 1 5
2 17
3 5

output

4
7
179
5
7
6

Note

In the first test case, one possible optimal sequence of operations is: $[1,3,3]\to [2,3,3]\to [2,4,3]\to [3,4,3]\to [4,4,3]$.

In the second test case, one possible optimal sequence of operations is: $[1,3,4,5,1]\to [1,4,4,5,1]\to [1,5,4,5,1]\to [1,5,5,5,1]\to [1,5,6,5,1]\to [1,6,6,5,1]\to [1,7,6,5,1]$.

$以上来自CodeForces$

题目翻译

给你一个长度为 $n$ 的整数数组 $a$ 。

在一次操作中，你

• 选择一个索引 $i$ ，使 $1\le i\le n?1$ 和 $a_i\le a_{i+1}$ .
• 将 $a_i$ 增加 $1$ 。

求最多执行 $k$ 次这一操作后， $\max (a_1,a_2,\dots a_n)$ 的最大可能值。

输入格式

每个测试包含多个测试用例。第一行输入包含一个整数 $t$ ( $1\le t\le 100$ ) - 测试用例的个数。测试用例说明如下。

每个测试用例的第一行包含两个整数 $n$ 和 $k$ （ $2\le n\le 1000$ ， $1\le k\le 10^8$ ）–数组的长度 $a$ 和可执行的最大操作数。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\dots ,a_n$ ( $1\le a_i\le 10^8$ ) - 数组 $a$ 的元素。

保证所有测试用例的 $n$ 之和不超过 $1000$ 。

输出格式

对每个测试用例输出一个整数，即数组最多执行 $k$ 次操作后的最大值。

提示

在第一个测试案例中，一个可能的最佳操作顺序是 $[1,3,3]\to [2,3,3]\to [2,4,3]\to [3,4,3]\to [4,4,3]$ .

在第二个测试案例中，一个可能的最佳操作序列是： $[1,3,4,5,1]\to [1,4,4,5,1]\to [1,5,4,5,1]\to [1,5,5,5,1]\to [1,5,6,5,1]\to [1,6,6,5,1]\to [1,7,6,5,1]$.

$翻译：DeepL$

解题思路

先看数据范围：$2\le n\le 1000$，那么直接使用贪心。

暴力思想

枚举最终成为答案的数 $a_i$。一开始肯定要利用 $a_{i+1}$ 让 $a_i$ 变得尽可能大，这样的代价是最小的。当 $a_i>a_{i+1}$ 时怎么办？利用 $a_{i+2}$ 让 $a_{i+1}$ 变大。

优化（贪心）

如果操作次数足够多，那么最终的序列肯定是形如 $x,x?1,?,a_n+1,a_n$ 的。也就是说，依次枚举 $j\in [i+1,n]$，当 $a_j\ge a_{j?1}$ 时，至多就可以让 $a_i$ 变大 $a_j?a_{j?1}+1$，此时更新答案即可。如果不满足，$a_j$ 在后续的更新过程中肯定要变成 $a_{j?1}?1$，否则无法使 $a_i$ 变得更大，提前更新 $a_j$ 即可。

时间复杂度 $O(n^2)$，写二分的是不是惊呆了。

AC Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int Maxn = 1000 + 5;
int n, k, a[Maxn];
int b[Maxn];
int ans;
inline int Binary_search(int n, int k);
inline void solve();
inline void work() {
	int T;
	cin >> T;
	while (T--) {
		solve();
	}
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	work();
	return 0;
}
inline void solve() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	ans = Binary_search(n, k);
	cout << ans << endl;
}
inline int Binary_search(int n, int k) {
	int tmp, t;
	int ans = a[n];
	for (int i = n - 1; i >= 1; i--) {
		for (int j = 1; j <= n; j++) {
			b[j] = a[j];
		}
		t = k;
		for (int j = i + 1; j <= n && t > 0; j++) {
			if (b[j] < b[j - 1]) {
				t -= b[j - 1] - 1 - b[j];
				b[j] = b[j - 1] - 1;
			} else {
				tmp = min(1ll * (b[j] - b[j - 1] + 1) * (j - i), t);
				t -= tmp;
				b[i] += tmp / (j - i);
			}
			ans = max(ans, b[i]);
		}
	}
	return ans;
}

吐槽一下洛谷对于该题的提示的染色问题。详见此处。