[CF1244E] Minimizing Difference - 贪心

有一个长度为 \(n\) 的序列，每次操作可以使其中的一个数 \(+1\) 或 \(-1\)。操作次数不得大于 \(k\)，问 \(MAX-MIN\) 的最小值是多少。

Solution

贪心，考虑到只有最大值和最小值对结果有影响，我们每次比较最大值和最小值的个数，动小的那一边

为了加速，每次动最小值时，看是否能将它修改为次小，如果不能则结束，最大值同理

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 200005;

int n,k,a[N],b[N],c[N],ind;
map<int,int> mp;

signed main() {
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i], mp[a[i]]++;
    for(auto i=mp.begin();i!=mp.end();i++) b[++ind]=i->first, c[ind]=i->second, i->second=ind;
    int l=1,r=n,ans=0;
    while(l<r) {
        if(c[l]<c[r]) {
            if(c[l]*(b[l+1]-b[l])<=k) {
                k-=c[l]*(b[l+1]-b[l]);
                c[l+1]+=c[l];
                c[l]=0;
                ++l;
            }
            else {
                ans=-k/c[l];
                break;
            }
        }
        else {
            if(c[r]*(b[r]-b[r-1])<=k) {
                k-=c[r]*(b[r]-b[r-1]);
                c[r-1]+=c[r];
                c[r]=0;
                --r;
            }
            else {
                ans=-k/c[r];
                break;
            }
        }
    }
    ans+=b[r]-b[l];
    cout<<ans;
}

[CF1244E] Minimizing Difference - 贪心

原文：https://www.cnblogs.com/mollnn/p/12617545.html