Codeforces Round #643 (Div. 2)E

这题的题意是你有n堆高为hi的砖你可以做三种操作1.花费a移除一个单位的的高度即（hi-1）,2.花费r在第i块砖上加一个单位的高度（hi+1）
3.花费m把第i堆上的一个挡位高度加到第j堆上（hi-1,hj+1），求最小花费使得这n堆砖块的高度相等。
思路：首先肯定我有这么一个想法--枚举高度，然后想了想不现实时间复杂度太高，又想是不是可以二分？既然看是不是可以二分就要看是不是单调函数，设答案高度是h0枚举出来的高度是h，当h接近h0时肯定是越接近花费越少，这样就意识到了好像不是二分，而是像一个二次函数，所以就是三分了。

• 这是一个三分的模板：（其实不管三分还是二分难点都是是否想到是不是三分或者二分还有check函数）

 while(r>=l)
   {
       int lmid=l+(r-l)/3;
       int rmid=r-(r-l)/3;
       ll ltemp=check(lmid);
       ll rtemp=check(rmid);
       if(ltemp<rtemp)
       {
           ans=ltemp;
           r=rmid-1;
       }
       else
       {
           ans=ltemp;
           l=lmid+1;
       }
   }

下面是ac代码 三分高度

#include<bits/stdc++.h>
#define ll long long
#define ms(a,b) memset(a,b,sizeof(a))
#define lowbit(x) x & -x
#define PI 3.1415926535898
#define bug cout<<"----acac----"<<endl
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
using namespace std;
const int maxn = 1e5 + 50;
const double eps = 1e-8;
const int INF = 0x3f3f3f3f;
const ll LNF  = 0x3f3f3f3f3f3f;
const int mod = 1e9 + 7;
int n,a,r,m;
ll h[maxn];
ll check(int mid)
{
    ll ma=0,mi=0;
    for(int i=1;i<=n;i++)
    {
        if(h[i]<mid)mi+=(mid-h[i]);
        if(h[i]>mid)ma+=(h[i]-mid);
    }
    ll res=min(mi,ma)*m;
    if(ma<mi)res+=a*(mi-ma);
    else res+=r*(ma-mi);
    return res;
}
int main()
{
   IOS;
   cin>>n>>a>>r>>m;
   for(int i=1;i<=n;i++)
        cin>>h[i];
    sort(h+1,h+1+n);
   m=min(m,a+r);//因为一次操作1和2等价于一个操作3，所以取最小值
   int l=h[1],r=h[n];
   ll ans=LNF;
   while(r>=l)
   {
       int lmid=l+(r-l)/3;
       int rmid=r-(r-l)/3;
       ll ltemp=check(lmid);
       ll rtemp=check(rmid);
       if(ltemp<rtemp)
       {
           ans=ltemp;
           r=rmid-1;
       }
       else
       {
           ans=ltemp;
           l=lmid+1;
       }
   }
   cout<<ans<<endl;
   return 0;
}