Description
你要修理一堵墙,这堵墙由 (N) 个宽度为一的砖块构成,其中第 (i) 块砖的高度为 (h_i) 。你需要执行下列操作让这 (N) 块砖的高度变得全部相等。
1、使一块砖的高度加一,这需要花费 (A) 的代价。
2、使一块高度为正的砖的高度减一,这需要花费 (R) 的代价。
3、使一块高度为正的砖的高度减一,另一块砖的高度加一,这需要花费 (M) 的代价。
给定 (N,A,R,M) ,你需要求出使所有砖的高度变得相同的最小代价。
Solution
首先将 (M) 对 (A+R) 取 (min),然后三分目标高度,能用 3 操作就先用 3 操作,剩下的用 2 操作。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000005;
int n,a,r,m,h[N];
int calc(int x)
{
int r0=0,r1=0;
for(int i=1;i<=n;i++)
{
if(h[i]>x) r1+=h[i]-x;
else r0+=x-h[i];
}
if(r1>r0) return m*r0+r*(r1-r0);
else return m*r1+a*(r0-r1);
}
int solve(int l,int r)
{
while(l<r)
{
int m1=(l*2+r)/3;
int m2=(l+r*2+2)/3;
if(calc(m1)>calc(m2)) l=m1+1;
else r=m2-1;
}
return l;
}
signed main()
{
ios::sync_with_stdio(false);
cin>>n>>a>>r>>m;
m=min(m,a+r);
for(int i=1;i<=n;i++) cin>>h[i];
int ans=solve(0,1e9);
cout<<calc(ans)<<endl;
}