分段枚举。

AC代码：

const int N = 2e5 + 50;
ll n, m, a, r;
ll h[N], sum[N], suf[N];

int main()
{
	cin >> n >> a >> r >> m;
	rep(i, 1, n)
		sld(h[i]);
	sort(h + 1, h + 1 + n);
	sum[0] = 0;
	rep(i, 1, n)
		sum[i] = sum[i - 1] + h[i];//前缀和
	suf[n + 1] = 0;
	per(i, n, 1)
		suf[i] = suf[i + 1] + h[i];//后缀和
	ll ans = INF;
	h[n + 1] = h[n];
	rep(i, 1, n)
	{
		ll p = i, s = n - i, tar;
		if (p * a <= s * r)
			tar = h[i + 1];
		else
			tar = h[i];
		ll add = p * tar - sum[i], remove = suf[i + 1] - s * tar;
		ll res = 0;
		if (a + r >= m)
		{
			ll tmp = min(add, remove);
			res += tmp * m, add -= tmp, remove -= tmp;
		}
		res += a * add + r * remove;
		ans = min(ans, res);
	}
	ll ave = sum[n] / n;
	rep(i, max(0ll, ave - 2), ave + 2)
	{
		ll add = 0, remove = 0;
		rep(j, 1, n)
		{
			if (h[j] < i)
				add += (i - h[j]);
			else if (h[j] > i)
				remove += (h[j] - i);
		}
		ll res = 0;
		if (a + r >= m)
		{
			ll tmp = min(add, remove);
			res += tmp * m, add -= tmp, remove -= tmp;
		}
		res += a * add + r * remove;
		ans = min(ans, res);
	}
	ans = min(ans, r * sum[n]);
	pld(ans);
	return 0;
}