Codeforces Round #592 (Div. 2) E - Minimizing Difference （最小差值）

?? ?? ??

题意：每次可以给一个数字加一或者减一，共k次操作，最后最大值减去最小值是多少。

以前写过一个类似的（然而以前的博客写的太乱实在找不到了），那个题是只能减少一，排序之后直接从后向前枚举即可。这题多了个加的操作，要从两边同时遍历。

1，假设数字排序之后以柱形图表示，并且在每次操作之后，将高度相等的柱形合并，该柱形宽度加一；

2，每次操作以最左/最右矩形的宽为单位操作，一次操作之后原答案减一，每次操作的代价即为矩形的宽，所以贪心选择最窄的矩形操作

3，每次操作一次肯定不行，尝试一次性操作多次后使原矩形宽度加一，若不足使矩形宽度增加，k肯定变为0，此时退出即可（虽然我没写

4，对答案有贡献只有最左最右两个矩形，如果只剩一个矩形答案为0；

vector<int>a;
int main()
{
    int n;ll k;cin>>n>>k;
    a.resize(n);cin>>a;
    sort(all(a)); 
    ll ans=a[n-1]-a[0];
    int l=0,r=n-1;
    while(l<r)
    {
        ll tmp=0;
        if(l+1<=n-r)
        {
            ++l;
            tmp=min(1ll*(a[l]-a[l-1]),k/l);//操作次数
            ans-=tmp;
            k-=1ll*tmp*l;
        }
        else
        {
            r--;
            tmp=min(1ll*(a[r+1]-a[r]),k/(n-r-1));
            ans-=tmp;
            k-=1ll*tmp*(n-r-1);
        }
    }
    cout<<ans<<endl;
    return  0;
}

Codeforces Round #592 (Div. 2) E - Minimizing Difference （最小差值）

原文：https://www.cnblogs.com/Herlo/p/12112991.html