P10957 环路运输
题目描述
在一条环形公路旁均匀地分布着NNN座仓库，编号为1∼N1 \sim N1∼N，编号为iii的仓库与编号为jjj的仓库之间的距离定义为dist(i,j)=min(∣i−j∣,N−∣i−j∣)dist(i,j)=\min(|i-j|,N-|i-j|)dist(i,j)=min(∣i−j∣,N−∣i−j∣)，也就是逆时针或顺时针从iii到jjj中较近的一种。
每座仓库都存有货物，其中编号为iii的仓库库存量为AiA_iAi。
在iii和jjj两座仓库之间运送货物需要的代价为Ai+Aj+dist(i,j)A_i+A_j+dist(i,j)Ai+Aj+dist(i,j)。
求在哪两座仓库之间运送货物需要的代价最大。
输入格式
第一行包含一个整数NNN。
第二行包含NNN个整数A1∼ANA_1 \sim A_NA1∼AN。
输出格式
输出一个整数，表示最大代价。
输入输出样例 #1
输入 #1
5 1 8 6 2 5输出 #1
15说明/提示
数据保证，2≤N≤1062 \le N \le 10^62≤N≤106，1≤Ai≤1071 \le A_i \le 10^71≤Ai≤107。
C++实现
#include<cstdio>#include<iostream>usingnamespacestd;constintN=2000010;typedeflonglongll;inta[N],q[N],h=1,t=0,n;ll ans;llMax(ll a,ll b){returna>b?a:b;}intmain(){scanf("%d",&n);for(inti=1;i<=n;i++){scanf("%d",&a[i]);a[i+n]=a[i];}intlen=n/2;q[++t]=1;for(inti=2;i<=n+len;i++){while(q[h]<i-len&&h<=t)h++;ans=Max(ans,(ll)(a[i]+i+a[q[h]]-q[h]));while(a[q[t]]-q[t]<a[i]-i&&t>=h)t--;q[++t]=i;}printf("%lld",ans);return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
)
