Codeforces 1355 E. Restorer Distance（三分）

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 
 5 ll p[100100];
 6 ll q[100100];
 7 ll n,a,b,c;
 8 
 9 ll check(ll sum)
10 {
11     ll ans=0,pp=0,qq=0;
12     for(ll i=1;i<=n;i++){
13         if(p[i]<sum) pp+=abs(p[i]-sum);
14         else qq+=p[i]-sum;
15     }
16     ans=min(pp,qq)*c+a*(pp-min(pp,qq))+b*(qq-min(pp,qq));
17     return ans;
18 }
19 
20 int main()
21 {
22     ios::sync_with_stdio(false);
23     cin.tie(0);
24     cout.tie(0);
25     cin>>n>>a>>b>>c;
26     for(ll i=1;i<=n;i++) cin>>p[i];
27     sort(p+1,p+n+1);
28     c=min(a+b,c);
29     ll l=0,r=1e9;
30     for(ll i=0;i<100;i++){
31         ll mid=l+(r-l)/3;
32         ll mid2=r-(r-l)/3;
33         if(check(mid)<=check(mid2)){
34             r=mid2;
35         }
36         else l=mid;
37     }
38     ll ans=0x3f3f3f3f3f3f3f3f;        //这个地方一定要开的足够大，不然会wa10
39     for(ll i=l;i<=r;i++) ans=min(ans,check(i));
40     cout<<ans<<endl;
41     return 0;
42 }