To Become Max
题面翻译
给定两个正整数 $n$ 和 $k$，以及一个长度为 $n$ 的序列 $a$，你可以进行不超过 $k$ 次如下操作（以下两个步骤合称一次操作）：
-
选择一个 $i$ 满足 $1 \le i < n$，且 $a_i \le a_{i + 1}$。
-
将 $a_i$ 增加 $1$。
求操作完成后，$\max \limits_{i = 1} ^ {n} a_i$ 的最大可以是多少。
多测，共 $t$ 组数据。
对于所有数据，保证 $1 \le t \le 100$，$1 \le n, \sum n \le 1000$，$1 \le k, a_i \le 10 ^ 8$。
题目描述
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, \ldots a_n) $ that you can get after performing this operation at most $ k $ times.
输入格式
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,\ldots,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 $ .
输出格式
For each test case output a single integer — the maximum possible maximum of the array after performing at most $ k $ operations.
样例 #1
样例输入 #1
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
样例输出 #1
4
7
179
5
7
6
提示
In the first test case, one possible optimal sequence of operations is: $[\textcolor{red}{1}, 3, 3] \rightarrow [2, \textcolor{red}{3}, 3] \rightarrow [\textcolor{red}{2}, 4, 3] \rightarrow [\textcolor{red}{3}, 4, 3] \rightarrow [4, 4, 3]$.
In the second test case, one possible optimal sequence of operations is: $[1, \textcolor{red}{3}, 4, 5, 1] \rightarrow [1, \textcolor{red}{4}, 4, 5, 1] \rightarrow [1, 5, \textcolor{red}{4}, 5, 1] \rightarrow [1, 5, \textcolor{red}{5}, 5, 1] \rightarrow [1, \textcolor{red}{5}, 6, 5, 1] \rightarrow [1, \textcolor{red}{6}, 6, 5, 1] \rightarrow [1, 7, 6, 5, 1]$.# To Become Max
题面翻译
给定两个正整数 $n$ 和 $k$，以及一个长度为 $n$ 的序列 $a$，你可以进行不超过 $k$ 次如下操作（以下两个步骤合称一次操作）：
-
选择一个 $i$ 满足 $1 \le i < n$，且 $a_i \le a_{i + 1}$。
-
将 $a_i$ 增加 $1$。
求操作完成后，$\max \limits_{i = 1} ^ {n} a_i$ 的最大可以是多少。
多测，共 $t$ 组数据。
对于所有数据，保证 $1 \le t \le 100$，$1 \le n, \sum n \le 1000$，$1 \le k, a_i \le 10 ^ 8$。
题目描述
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, \ldots a_n) $ that you can get after performing this operation at most $ k $ times.
输入格式
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,\ldots,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 $ .
输出格式
For each test case output a single integer — the maximum possible maximum of the array after performing at most $ k $ operations.
样例 #1
样例输入 #1
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
样例输出 #1
4
7
179
5
7
6
提示
In the first test case, one possible optimal sequence of operations is: $[\textcolor{red}{1}, 3, 3] \rightarrow [2, \textcolor{red}{3}, 3] \rightarrow [\textcolor{red}{2}, 4, 3] \rightarrow [\textcolor{red}{3}, 4, 3] \rightarrow [4, 4, 3]$.
In the second test case, one possible optimal sequence of operations is: $[1, \textcolor{red}{3}, 4, 5, 1] \rightarrow [1, \textcolor{red}{4}, 4, 5, 1] \rightarrow [1, 5, \textcolor{red}{4}, 5, 1] \rightarrow [1, 5, \textcolor{red}{5}, 5, 1] \rightarrow [1, \textcolor{red}{5}, 6, 5, 1] \rightarrow [1, \textcolor{red}{6}, 6, 5, 1] \rightarrow [1, 7, 6, 5, 1]$.
像这种操作数导致数值大到离谱的就二分
const int N = 2e5 + 10;
int n, kk;
int a[N];
int cheak(int x,int xb)
{
int k = kk;
int top = x;
int ok = 0;
for (int i = xb; i <= n; i++)
{
if (a[i] >= top)
{
ok = 1;
break;
}
int ca = top - a[i];
if (k >= ca)
{
k -= ca;
}
else
{
break;
}
top--;
}
if (ok) return 1;
else return 0;
}
void solve()
{
int mmax = 0;
cin >> n >> kk;
for (int i = 1; i <= n; i++) cin >> a[i], mmax = max(mmax, a[i]);
for (int i = 1; i <= n; i++)
{
int l = a[i] + 1, r = a[i] + kk;
while (l <= r)
{
int mid = (l + r) / 2;
if (cheak(mid,i))
{
mmax = max(mmax, mid);
l = mid + 1;
}
else r = mid - 1;
}
}
cout << mmax << '\n';
}
