比较有趣的题。考虑到问题问的是“第 大的值最大是多少”，于是容易想到二分这个最大值，问题在于怎么 check 是否合法。
注意到问题最多只会加一个等差数列，所以考虑对等差数列做一个滑动窗口，然后从左往右扫描整个数组，此时每一个位置的值的变化形如：
- 保持原来的值。
- 变为全过程的最大值。
- 逐渐变小。
- 变回原来的值。
那么二分之后套路的把序列转为一个 序列，这样一来在滑动这个窗口的过程中，每一个位置的 值只存在下面的三种情况：
- 始终保持 。
- 始终保持 。
- 一开始值为 ，在遇到窗口的时候值变为 ，在窗口继续右移的某个时刻中变回 。
前面两种容易统计，第三种求出变回 的时刻可以简单二分处理或直接推数学公式，总时间复杂度为 或 均可通过该题。这里给出 算法的实现：
// #pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
using namespace std;
const int N = 1000010;
const int inf = 1e18;
const int mod = 998244353;
int a[N], b[N], l[N], r[N], vis[N], dep[N], buc[N];
int n, k, m, c, d, diff[N];
inline int chk(int x)
{
int _;
if ((_ = count_if(a + 1, a + n + 1, [&](int &o) { return o >= x; })) >= k)
return 1;
fill(diff, diff + n + 5, 0);
for (int i = 1; i <= n; ++i)
if (a[i] < x && a[i] + c + d * min(i - 1, m - 1) >= x)
{
++diff[max(i, m)];
if (a[i] + c >= x)
{
if (m + i <= n)
--diff[m + i];
}
else
{
int id = ((x - a[i] - c) % d == 0) ? ((x - a[i] - c) / d - 1) : ((x - a[i] - c) / d);
if (m + i - id - 1 <= n)
--diff[m + i - id - 1];
}
}
for (int i = m; i <= n; ++i)
if ((_ += diff[i]) >= k)
return 1;
// if (x == 4)
// cerr << "at last _ = " << _ << '\n';
return 0;
}
signed main()
{
cin.tie(0)->sync_with_stdio(false);
cin >> n >> k >> m >> c >> d;
for (int i = 1; i <= n; ++i)
cin >> a[i];
int l = 0, r = 1e18, best = -1;
while (l <= r)
{
int mid = l + r >> 1;
chk(mid) ? (l = mid + 1, best = mid) : (r = mid - 1);
}
cout << best << '\n';
return 0;
}
喜欢的话，留下你的评论吧～