【三分模板】Codeforces Round #643 (Div. 2) E. Restorer Distance

本文主要是介绍【三分模板】Codeforces Round #643 (Div. 2) E. Restorer Distance，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

三分模板题，最小化值

#include<bits/stdc++.h>
#define mem(x) memset(x,0,sizeof(x))
using namespace std;
typedef long long ll;
const ll maxn=1e5+10;
const ll mod=1e9+7;
const ll inf=0x7f7f7f7f;
template<typename T>void read(T &x)
{x = 0;char ch = getchar();ll f = 1;while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T>void write(T x)
{if(x<0){putchar('-');x=-x;}if(x>9){write(x/10);}putchar(x%10+'0');
}
ll T,n,a,m,r,cl,cr,midl,midr,l,rr,ans=0;
ll mp[maxn];
bool flag;
ll check(ll mid)
{ll ans=0,up=0,down=0;for(int i=1;i<=n;i++){if(mp[i]<mid){up+=mid-mp[i];}else{down+=mp[i]-mid;}}ans=a*up+r*down;ll x=min(up,down);if(a+r>m){ans+=(m-a-r)*x;}return ans;
}
int main()
{read(n);read(a);read(r);read(m);for(int i=1;i<=n;i++){read(mp[i]);}l=0;rr=1e9;while(l<rr){midl=(rr-l)/3+l;midr=rr-(rr-l)/3;cl=check(midl);cr=check(midr);if(cl>cr){l=midl+1;}else{rr=midr-1;}}ans=check(l);printf("%lld",ans);return 0;
}

这篇关于【三分模板】Codeforces Round #643 (Div. 2) E. Restorer Distance的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---