题目描述
blablabla
样例
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<string>
#include<cstring>
using namespace std;
const int N = 1e5 + 100;
int arr[N],brr[100];
typedef long long LL;
/*
题解:
采用二分算法;
此处的最佳答案是未知的。
假设最佳答案是h,那么数组中一定有h,h-1,h-2.。。。诸如此类的一段数组元素。
而,h的大小范围是1——(数组最大元素+k)
当然原生数组一般不会刚好是上面所描述的那种最佳准状态,需要我们去构造。
二分的check函数就是看能不能构造出来最佳状态来。
因为不知道h的具体位置,就吧所有数组元素都拿来二分一下。
从1开始一直到n;
*/
int t, n, k;
bool check(LL u, LL h) {
int kk = k;
for (int i = u; i <= n; i++,h--) {
if (h <= arr[i])return true;
kk -= h - arr[i];
if (kk < 0)return false;
}
return false;
}
int main() {
cin >> t;
while (t--) {
cin >> n >> k;
int mass= -1;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
mass = max(mass, arr[i]);
}
for (int i = 1; i <= n; i++) {
int l = 1, r = 1e9;
while (l <= r) {
int mid = (l + r) / 2;
if (check(i, mid)) {
l = mid + 1;
}
else r = mid - 1;
}
mass = max(mass, r);
}
cout << mass << endl;
}
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla