G题 赛题补充
D题的题目来源 https://codeforces.com/gym/104128/problem/D
文章目录
题意
给一个长度为n的数组，问对一段区间添加等差数列后的最大的第 k 大是多少
思路
- 通过观察题目可以发现答案的范围符合单调性，因此我们可以考虑二分，那么第K大的数>=mid 等效于 有超过k个>=mid的数
- 主要就是利用等差数列的性质和差分的思想去维护cf这个差分数组
- 对于第k大,只要进行前缀和处理后区间>=mid的个数多于k个即可
代码
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define fi first
#define se second
#define PII pair<int,int>
using namespace std;
const int N=2e5+5;
int a[N];
int n,k,m,c,d;
int cf[N];
bool check(int x){
memset(cf,0,sizeof cf);
for(int i=1;i<=n;++i){
if(a[i]>=x){
cf[1]++;//a[i]大于等于x，直接加上它的个数
}
else{
int l=max(i-m+1,1LL);//l代表等差数列最远可到的左端点
if(a[i]+c+(i-l)*d<x) continue;//加完若还不大于等于x，那么它肯定不满足题意
int j;//j表示需要加几次公差才能大于等于x
int minn=a[i]+c;//先加上首项
if(d==0) j=0;
else j=(x-minn-1)/d+1;
j=max(j,0LL);//j最低为0
int r=i-j;//差分的右端点
++cf[l];
--cf[r+1];
}
}
for(int i=1;i<=n;++i) cf[i]+=cf[i-1];//前缀和处理
int ans=0;
for(int i=1;i<=n;++i) ans=max(ans,cf[i]);
if(ans>=k) return true;//ans大于等于k，符合条件
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>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
cout << l << endl;
return ;
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t=1;
//cin >> t;
while(t--) solve();
return 0;
}
```cpp