数组操作

Description

小红拿到了一个数组，她每次可以进行如下操作：
选择一个数，使其减去 $x$ 。
小红希望 $k$ 次操作之后，该数组的最大值尽可能小。请你求出这个尽可能小的最大值。

Input

$\begin{matrix} n & k & x \\ a_{1} & a_{2} & \dots & a_{n} \end{matrix}$
数据范围：
$1 \leq n \leq 10^{5}$
$1 \leq a_{i}, k, x \leq 10^{9}$

Output

一个整数，代表 $k$ 次操作后，数组尽可能小的最大值。

Sample Input

5 3 5
4 3 11 2 1

Sample Output

Notes

第一个数操作 $1$ 次，第三个数操作 $2$ 次，数组变成 $[- 1, 3, 1, 2, 1]$ ，最大值为 $3$ 。

Solution

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,x,a[100010];
bool check(int mid){
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(a[i]>mid)cnt+=(a[i]-mid+x-1)/x;
        if(cnt>k)return false;
    }
    return true;
}
signed main(){
    cin>>n>>k>>x;
    for(int i=1;i<=n;i++)cin>>a[i];
    int l=-1e18,r=1e9;
    while(l<r){
        int mid=l+r-1>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    cout<<r<<'\n';
}