1：题意
给你一个序列要求你进行一次操作，选一个位置i从他开始往后加数直到加到第i+m-1个，加的值成等差求操作完后的第k大的数
2：思路
1）:二分答案
二分找到第k大的值
2）：差分
check里面，枚举每一个数看他是否大于mid，记录为num，小于的判断他是否+等差最后一位小于mid，小于直接跳过，大于则判断他可以在那一个位置，然后把他这个区间表示出来，即贡献度，再前缀和一下就可以了
代码
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
typedef long long ll;
int a[N];
int n,m,k,c,d;
bool check(int mid)
{
vector<int>f(n+2,0);
int num = 0;
for(int i = 1;i <= n;i ++)
{
if(a[i] >= mid)
num++;
else if(a[i] + c + d*(m-1) < mid )
continue;
else
{
int cnt = 0;
if(d)
{
int tmp = a[i]+c;
cnt = (mid - tmp + d - 1)/d;
cnt = max(0LL,cnt);
}
f[max(0LL,(i-m+1))]++;
f[min(n+1,max(0LL,i - cnt+1))]--;
}
}
int mx = 0;
for(int i = 1;i <= n;i ++)
{
f[i] += f[i-1];
mx = max(mx,f[i]);
}
if(mx + num >= k)
return true;
else
return false;
}
void solve()
{
cin >> n >> k >> m >> c >> d;
for(int i = 1;i <= n;i ++)
cin >> a[i];
int l = 0,r = 1e18;
while(l < r)
{
int mid = (l+r+1)/2;
if(check(mid))
l = mid;
else
r = mid - 1;
//cout << l << ' ' << r << '\n';
}
cout << l << '\n';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
solve();
}