在网上做效果图网站,怎么做网站滑动图片部分,游戏开发软件有哪些,做网站在阿里云上面买哪个服务G题 赛题补充 D题的题目来源 https://codeforces.com/gym/104128/problem/D 文章目录 题意思路代码 题意
给一个长度为n的数组#xff0c;问对一段区间添加等差数列后的最大的第 k 大是多少
思路
通过观察题目可以发现答案的范围符合单调性#xff0c;因此我们可以考虑二分…G题 赛题补充 D题的题目来源 https://codeforces.com/gym/104128/problem/D 文章目录 题意思路代码 题意
给一个长度为n的数组问对一段区间添加等差数列后的最大的第 k 大是多少
思路
通过观察题目可以发现答案的范围符合单调性因此我们可以考虑二分那么第K大的数mid 等效于 有超过k个mid的数主要就是利用等差数列的性质和差分的思想去维护cf这个差分数组对于第k大,只要进行前缀和处理后区间mid的个数多于k个即可
代码
#includebits/stdc.h
#define int long long
#define endl \n
#define fi first
#define se second
#define PII pairint,int
using namespace std;
const int N2e55;
int a[N];
int n,k,m,c,d;
int cf[N];
bool check(int x){memset(cf,0,sizeof cf);for(int i1;in;i){if(a[i]x){cf[1];//a[i]大于等于x直接加上它的个数}else{int lmax(i-m1,1LL);//l代表等差数列最远可到的左端点if(a[i]c(i-l)*dx) continue;//加完若还不大于等于x那么它肯定不满足题意int j;//j表示需要加几次公差才能大于等于xint minna[i]c;//先加上首项if(d0) j0;else j(x-minn-1)/d1;jmax(j,0LL);//j最低为0int ri-j;//差分的右端点cf[l];--cf[r1];}}for(int i1;in;i) cf[i]cf[i-1];//前缀和处理int ans0;for(int i1;in;i) ansmax(ans,cf[i]);if(ansk) return true;//ans大于等于k符合条件return false;
}
void solve(){ cin n k m c d;for(int i1;in;i){cin a[i];}int l0,r1e18;while(lr){//二分求右边界int midlr11;if(check(mid)) lmid;else rmid-1;}cout l endl;return ;
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t1;//cin t;while(t--) solve();return 0;
}
cpp
