CF1244E Minimizing Difference

@Pelom  October 11, 2021

题意

给出$n$个数,每次操作可以选择一个数$+1$或$-1$,求$k$次操作后最小极差

数据范围:$2 \le n \le 10^5,1 \le k \le 10^{14}$

题解

为了减小极差,每次肯定是选择最大值$-1$或最小值$+1$,所以先排个序
为了快速转移,可以将$a[i]$变为$a[i+1]$(对于前半部分)或将$a[i]$变为$a[i-1]$(对于后半部分);而当$k$值不足以进行一次转移时,还可以给之前已经处理过的数(相等且最大/最小)整体改变
为了避免选择改变最大值还是最小值,将其放到一起处理;注意偶数项的中间两项需要特殊处理,避免算重

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
const int N=1e5+10;
int n,k;
int a[N];
int ans;
signed main(){
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    sort(a+1,a+n+1);
    ans=a[n]-a[1];
    for(int i=1;i<(n+1)/2;i++){
        int t=min(a[i+1]-a[i]+a[n-i+1]-a[n-i],k/i);
        ans-=t;
        k-=t*i;
    }
    if(n%2==0){
        int t=min(a[n/2+1]-a[n/2],k/(n/2));
        ans-=t;
        k-=t*(n/2);
    }
    printf("%lld",ans);
    return 0;
}

添加新评论