The 2022 ICPC Asia Nanjing Regional Contest - External D

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表示需要加几次公差才能大于等于xint minn=a[i]+c;//先加上首项if(d==0) j=0;else j=(x-minn-1)/d+1;j=max(j,0LL);//j最低为0int 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