CVBB ACM Team

有$n$个用$a$_$i$个相同的砖垒成的柱子，有三种操作：$add$ 给一个柱子加一块砖，代价为$a$ ,$remove$ 给一个柱子减一块砖，代价为$r$，$move$ 将一个柱子的砖块移动到另一个柱子上，代价为$m$，问当$n$个柱子高度相同时的最少代价

现对输入的砖块高度进行排序，$m$取$a+r$和$m$的最小值以保证代价最少 ，然后用三分法得到结果。很神奇 ~~~

#include <bits/stdc++.h>
#define ll long lnog
using namespace std;
 
ll p[100010];
ll n, a, r, m;
ll f(ll mid) {
    ll ct1, ct2; 
    ct1 = ct2 = 0;
    for (ll i = 1; i <= n; i++)
        if (p[i] < mid)
            ct1 += mid - p[i];
        else
            ct2 += p[i] - mid;
    ll ct3 = min(ct1, ct2); 
    ct1 -= ct3, ct2 -= ct3;
    return ct1 * a + ct2 * r + ct3 * m;
}
int main() {
    cin >> n >> a >> r >> m;
    m = min(a + r, m);
    for (ll i = 1; i <= n; i++)
        cin >> p[i];
    sort(p + 1, p + 1 + n);
 
    ll l = 0, r = 1000000000;
    while (l < r) {
        // ll mid = l + r >> 1;
        // ll midr = mid + r >> 1;
        ll mid = l + (r - l) / 3; 
        ll midr = l + (2 * r - 2 * l + 2) / 3;
        if (f(mid) > f(midr))
            l = mid + 1;
        else
            r = midr - 1;
    }
    cout << f(l) << endl;
    return 0;
}