CF gym102483 A. Access Points
2022/2/4 23:19:55
本文主要是介绍CF gym102483 A. Access Points,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题面传送门
首先距离的平方等于\(x\)轴平方加上\(y\)轴平方。所以\(x,y\)轴独立。
然后考虑\(x\),如果\(x\)单调递增,那么直接令所有位置都在\(x\)上即可。
但是不会这样,如果\(x\)是单调下降的,通过简单的二次函数,我们可以知道这一段应该被赋值成同一个值,为\(\frac{\sum\limits_{i=a}^{b}{x_i}}{b-a}\),即这一段的平均数。
但是还有一个要求就是\(x\)递增,不难发现直接维护一个单调栈合并即可。
时间复杂度\(O(n)\)
code:
#include<bits/stdc++.h> #define I inline #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) #define abs(x) ((x)>0?(x):-(x)) #define re register #define RI re int #define ll long long #define db double #define lb long db #define N 100000 #define M N*N+5 #define mod 998244353 #define Mod (mod-1) #define eps (1e-5) #define U unsigned int #define it iterator #define Gc() getchar() #define Me(x,y) memset(x,y,sizeof(x)) #define d(x,y) (m*x+(y)) #define R(n) (rand()*rand()%(n)+1) #define Pc(x) putchar(x) #define LB lower_bound #define UB upper_bound using namespace std; int n,m,k,st[N+5],H;db ToT,x[N+5],y[N+5],A[N+5],Q[N+5]; I db calc(int j,int i){return (Q[i]-Q[j])/(i-j);} I db Solve(){ db Ans=0;RI i;H=0;for(i=1;i<=n;i++){Q[i]=Q[i-1]+A[i];Ans+=A[i]*A[i]; while(H&&calc(st[H-1],st[H])>calc(st[H],i)) H--;st[++H]=i; }for(i=1;i<=H;i++) Ans-=calc(st[i-1],st[i])*calc(st[i-1],st[i])*(st[i]-st[i-1]);return Ans; } int main(){ freopen("1.in","r",stdin); scanf("%d",&n);for(RI i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]);memcpy(A,x,sizeof(x));ToT+=Solve();memcpy(A,y,sizeof(y));printf("%.8lf\n",Solve()+ToT); }
这篇关于CF gym102483 A. Access Points的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01巧用 TiCDC Syncpoint 构建银行实时交易和准实时计算一体化架构
- 2024-05-01银行核心背后的落地工程体系丨Oracle - TiDB 数据迁移详解
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享
- 2024-04-14result 成功怎么写-icode9专业技术文章分享