Restorer Distance

Created by LXC on Sun Mar 10 18:00:35 2024

https://codeforces.com/problemset/problem/1355/E

ranting: 2100

tag: binary search, greedy, math, sortings, ternary search

problem

你要修理一堵墙，这堵墙由 $N$ 个宽度为一的砖块构成，其中第 $i$ 块砖的高度为 $h_i$ 。你需要执行下列操作让这 $N$ 块砖的高度变得全部相等。

1、使一块砖的高度加一，这需要花费 $A$ 的代价。

2、使一块高度为正的砖的高度减一，这需要花费 $R$ 的代价。

3、使一块高度为正的砖的高度减一，另一块砖的高度加一，这需要花费 $M$ 的代价。

给定 $N,A,R,M$ ，你需要求出使所有砖的高度变得相同的最小代价。

solution

我们将h升序排序，对于第i个数左侧和第i个数右侧，我们可以选择$h_i$到$h_{i+1}$之间的数m，然后将所有数字变为x。

不妨设$ps_i$为升序后h的前i个数的和。

记i及左侧的数的个数为l，i右侧的数的个数为r，左侧和为$sl=ps_i$, 右侧和为$sr=ps_{N}-ps_l$，左侧需要的数的个数是$a=l\times m-sl$，右侧移除的个数是$b=sr- r\times m$

如果添加和移除的费用加起来都小于移动的费用，那么移动操作我们永远不会用到。此时的花费是$a\times A + b\times R$；否则将有$mn = min(a, b)$个可以通过移动从右侧移动到左侧，需要的花费是$(a-mn)\times A + (b-mn)\times R + mn\times M$。

花费从$h_i$到$h_{i+1}$应是凹函数，三分法求最小值。对于每个i的维护最小值便是答案。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    int N, A, R, M;
    cin >> N >> A >> R >> M;
    vector<ll> h(N+1);
    for (int i=1; i<=N; i++) {
        cin >> h[i];
    }
    sort(h.begin()+1, h.end());
    vector<ll> ps(N+1);
    for (int i=1; i<=N; i++) {
        ps[i] = ps[i-1] + h[i];
    }
    // cout << h << endl;
    auto cal = [&](ll sp, ll m) {
        ll l = sp, r = N-sp;
        ll sl = ps[l], sr = ps[N]-ps[l];
        ll a = l*m-sl, b = sr-r*m;
        ll mn = A+R<M?0L:min(a, b);
        // cout << "sp " << sp << endl;
        // cout << "m " << m << endl;
        // cout << "l " << l << endl;
        // cout << "r " << r << endl;
        // cout << "sl " << sl << endl;
        // cout << "sr " << sr << endl;
        // cout << "a " << a << endl;
        // cout << "b " << b << endl;
        // cout << "mn " << mn << endl;
        // cout << "cal " << A*(a-mn) + R*(b-mn) + M*(mn) << endl;
        // cout << endl;
        return A*(a-mn) + R*(b-mn) + M*(mn);
    };
    ll ans = 1e18;
    for (int i=1; i<N; i++) {
        ll l = h[i], r = h[i+1], lans, rans;
        while (l<r) {
            ll lmid = l + (r-l)/3;
            ll rmid = r - (r-l)/3;
            lans = cal(i, lmid), rans = cal(i, rmid);
            if (lans <= rans) r = rmid-1;
            else l = lmid + 1;
        }
        // cout << "i: " << i << " ans: " << min(lans, rans) << endl;
        ans = min(ans, min(lans, rans));
    }
    cout << ans%((ll) 1e18) << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}