题目描述

您是国际聊天程序公司（International Chatting Program Company，ICPC）的研究员。今天，您在浏览研究数据时，发现了以下聊天记录。

SUA（2022/12/04 23:01:25）

我已经用光了程序设计竞赛题目的点子！请给我一道关于序列的题目。

机器人（2022/12/04 23:01:27）

当然可以，下面是一道关于序列的程序设计竞赛的题目。

给定一个长度为 n 的整数序列 a1​,a2​,⋯,an​，同时给定另外四个整数 k，m，c 与 d，您的目标是最大化序列中第 k 大的值。

为了达成这一目标，您可以进行以下操作至多一次：选择一个长度恰为 m 的连续子数组，并将一个长度为 m，首项为 c，公差为 d 的等差序列加到该连续子数组上。

更正式地，您可以选择一个整数 p 满足 1≤p≤n−m+1，并对于所有 0≤i<m，将 ap+i​ 增加 (c+di)。

求至多一次操作之后，序列中第 k 大的值最大可能是多少。

序列中第 k 大的值，指的是将序列从大到小排序后，位于序列第 k 项的值。例如，序列 {5,7,1,9} 中，第 3 大的值为 5；而序列 {9,7,5,9} 中，第 3 大的值为 7。

SUA（2022/12/05 00:15:17）

这道题目好像很难！请告诉我它的解法。

机器人（2022/12/05 00:15:30）

当然可以。首先，我们可以...

[数据删除]

遗憾的是，部分聊天记录由于硬盘损坏而丢失了。您为聊天程序可以创造程序设计竞赛的题目而感到非常惊奇。为了验证聊天程序是否能创造有效的题目，您决定尝试解决这道题目。

输入格式

每个测试文件仅有一组测试数据。

第一行输入五个整数 n，k，m，c 和 d（1≤k,m≤n≤2×105，0≤c,d≤109）表示序列的长度，您的目标，等差序列的长度，首项和公差。

第二行输入 n 个整数 a1​,a2​,⋯,an​（0≤ai​≤109）表示给定的序列。

输出格式

输出一行一个整数，表示至多一次操作之后，序列中第 k 大的值最大可能是多少。

输入输出样例

输入 #1复制

6 4 3 1 2
1 1 4 5 1 4

输出 #1复制

4

输入 #2复制

7 3 2 4 0
1 9 1 9 8 1 0

输出 #2复制

9

输入 #3复制

8 3 5 0 0
2 0 2 2 1 2 1 8

输出 #3复制

2

说明/提示

对于第一组样例数据，可以选择 p=3 使序列变为 {1,1,5,8,6,4}。序列中第 4 大的值为 4。

对于第二组样例数据，可以选择 p=5 使序列变为 {1,9,1,9,12,5,0}。序列中第 3 大的值为 9。

对于第三组样例数据，容易发现操作不改变序列的值，因此我们选择不进行操作。序列中第 3 大的值为 2。

OpenAI ChatGPT 正在鼓励选手

思路

二分判断能否，内部贪心即可。

代码见下

#include<bits/stdc++.h>
using namespace std;
long long n,k,m,c,d,a[200005],st[200005];
bool abc(long long a1){
    for(int i=0;i<=n;i++){
        st[i]=0;
    }
    for(int i=1;i<=n;i++){
        if(a[i]>=a1){
            st[1]++;
        }
        else if(a[i]+c+min(m-1,(long long)i-1)*d>=a1){
            st[max(1ll,i-m+1)]++;
            if(d!=0){
                st[min((long long)i,i-(a1-a[i]-c+d-1)/d)+1]--;
            }
            else{
                st[i+1]--;
            }
        }
    }
    long long gh=0,qd=0;
    for(int i=1;i<=n-m+1;i++){
        gh+=st[i];
        if(gh>=k){
            qd=1;
        }
    }
    return qd;
}
int main(){
    cin>>n>>k>>m>>c>>d;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    long long l=0,r=1e18+7,md=0;
    while(l<=r){
        long long mid=(l+r)/2;
        if(abc(mid)==1){
            md=max(md,mid);
            l=mid+1;
        }
        else{
            r=mid-1;
        }
    }
    cout<<md<<endl;
	return 0;
}