[CF 1355E] Restorer Distance

题目链接：http://oj.daimayuan.top/course/22/problem/977

学三分的时候碰到了WLS的这题。WLS说是证明了一个多小时才证明出来的。我这里大致解释一下，因为我也不是很懂。。。。 

思路：

这里先贪心一下。因为操作3是操作1和操作2的合并，所以我们先试着了解一下，如果A+R<M的，那就说明，就不需要操作3，因为操作1和操作2的合并也能实现操作3的功能且所花费的代价更小。

三分：不断分割不必要的部分，经过多次，会得到一个小区间【L，L+1，R】，那么最小代价一定是在这个区间里的某点上。WLS的意大概是，不断的分割，会形成一个单谷函数，那么最后所得的小区间，一定是包含了极值点。具体证明捏，请教WLS吧。

代码：

#include<bits/stdc++.h>
#define int long long
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N=2e5+10;
int a[N];
int n,A,R,M;int f(int x){//表示最终统一的值int y=0,z=0;//y：执行操作1的个数  z：执行操作2的个数for(int i=1;i<=n;i++){if(a[i]<=x) y+=x-a[i];else z+=a[i]-x;}int res=min(y,z)*M;//执行合并的次数if(y>z) res+=(y-z)*A;else res+=(z-y)*R;return res;
}inline void solve(){cin>>n>>A>>R>>M;for(int i=1;i<=n;i++) cin>>a[i];M=min(M,A+R);int l=0,r=1e9;while(l+2<r){int M1=(r-l)/3+l;int M2=(r-l)/3*2+l;if(f(M1)>f(M2)) l=M1;//M1左段没有用else r=M2;//M2右段没有用}int ans=f(l);for(int i=l+1;i<=r;i++) ans=min(ans,f(i));cout<<ans<<"\n";
}signed main(){fast;//int T;cin>>T;//while(T--) solve();
}

这里再解释一下，这里三分的结果，不是一个具体的点，而是某些答案可能值的点的区间，所以不用考虑边界问题，因为，最后是把含边界的点都通过暴力的方式进行求值了

ps：这题三分用的真的是秒！WLS yyds！