CodeForces 1355E :Restorer Distance 三分
2021/4/30 18:57:31
本文主要是介绍CodeForces 1355E :Restorer Distance 三分,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
传送门
题目描述
你要修理一堵墙,这堵墙由
N
N
N 个宽度为一的砖块构成,其中第
i
i
i 块砖的高度为
h
i
h_{i}
hi 。
你需要执行下列操作让这
N
N
N块砖的高度变得全部相等。
- 1、使一块砖的高度加一,这需要花费 A A A 的代价。
- 2、使一块高度为正的砖的高度减一,这需要花费 R R R 的代价。
- 3、使一块高度为正的砖的高度减一,另一块砖的高度加一,这需要花费 M M M 的代价。
给定 N N N, A A A, R R R, M M M ,你需要求出使所有砖的高度变得相同的最小代价。
分析
首先3操作可以转换成一个1操作和一次2操作,只需要看 A + R A + R A+R和 M M M的大小关系,然后如果我们把最后留下来的高度设置的过大或者过小,那么需要操作的次数就会更多,所以盲猜这是一个凹函数,可以用三分法求一下极点范围,从而求最小值
代码
#pragma GCC optimize(3) #include <bits/stdc++.h> #define debug(x) cout<<#x<<":"<<x<<endl; #define dl(x) printf("%lld\n",x); #define di(x) printf("%d\n",x); #define _CRT_SECURE_NO_WARNINGS #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> PII; typedef vector<int> VI; const int INF = 0x3f3f3f3f; const int N = 2e5 + 10; const ll mod= 1000000007; const double eps = 1e-9; const double PI = acos(-1); template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;} int gcd(int a,int b){return (b>0)?gcd(b,a%b):a;} ll a,b,c; ll h[N]; int n; ll check(int x){ ll sum1 = 0,sum2 = 0; for(int i = 1;i <= n;i++) if(h[i] < x) sum1 += x - h[i];else sum2 += h[i] - x; ll ans = 0; if(c < a + b){ ll t = min(sum1,sum2); ans += t * c; sum1 -= t,sum2 -= t; } ans += sum1 * a; ans += sum2 * b; return ans; } int main(){ read(n),read(a),read(b),read(c); for(int i = 1;i <= n;i++) read(h[i]); ll l = 1,r = 1e9 + 10; while(r - l > 10) { ll lmid = l + (r - l) / 3; ll rmid = r - (r - l) / 3; ll lans = check(lmid),rans = check(rmid); if(lans <= rans) r = rmid - 1; else l = lmid + 1; } ll ans = 0x3f3f3f3f3f3f3f3f; for(int i = l;i <= r;i++) ans = min(ans,check(i)); dl(ans); return 0; } /** * ┏┓ ┏┓+ + * ┏┛┻━━━┛┻┓ + + * ┃ ┃ * ┃ ━ ┃ ++ + + + * ████━████+ * ◥██◤ ◥██◤ + * ┃ ┻ ┃ * ┃ ┃ + + * ┗━┓ ┏━┛ * ┃ ┃ + + + +Code is far away from * ┃ ┃ + bug with the animal protecting * ┃ ┗━━━┓ 神兽保佑,代码无bug * ┃ ┣┓ * ┃ ┏┛ * ┗┓┓┏━┳┓┏┛ + + + + * ┃┫┫ ┃┫┫ * ┗┻┛ ┗┻┛+ + + + */
这篇关于CodeForces 1355E :Restorer Distance 三分的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-30uniAPP 实现全屏左右滚动滚动的效果-icode9专业技术文章分享
- 2024-06-30如何在本地使用授权或插件-icode9专业技术文章分享
- 2024-06-30伪静态规则配置方法汇总-icode9专业技术文章分享
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding