数组操作 | FXJFXJ

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

## Input \(\boxed{\begin{array}&n&k&x\\a_{1}&a_{2}&\dots&a_{n}\end{array}}\) 数据范围： \(1\leq n\leq 10^5\) \(1\leq a_{i},k,x\leq 10^9\)

Output

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

Sample Input

1 2	5 3 5 4 3 11 2 1

Sample Output

Notes

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

Solution

![[../../../../images/Z-attachment/Pasted image 20231228143934.png]]

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';
}