[CF 1355E] Restorer Distance

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

代码：

#include
#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+2f(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<>T;//while(T--) solve();
}

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

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

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！