[atAGC044E]Random Pawn

记$ans_{i}$为初始位于$i$的答案，显然有$ans_{i}=\max(a_{i},\frac{ans_{i-1}+ans_{i+1}}{2}-b_{i})$

通过旋转，不妨假设$\forall 1\le i

此时，显然有$ans_{0}=ans_{n}=a_{0}$，即首尾并不需要转移，问题变为了一条链

构造一组$\{c_{i}\}$，记$s_{i}=ans_{i}-c_{i}$，代入可得$s_{i}=\max(a_{i}-c_{i},\frac{(s_{i-1}+c_{i-1})+(s_{i+1}+c_{i+1})}{2}-(b_{i}+c_{i}))$

若$\{c_{i}\}$满足$\frac{c_{i-1}+c_{i+1}}{2}=b_{i}+c_{i}$，那么上式也即$s_{i}=\max(a_{i}-c_{i},\frac{s_{i-1}+s_{i+1}}{2})$

注意到此时的$s_{i}$即$(i,a_{i}-c_{i})$构成的上凸包中$i$处的值，直接计算即可，最后再加上$c_{i}$即得到$ans_{i}$

关于如何使$c_{i}$满足该式子，注意到$c_{0}$和$c_{n}$是任意的，直接令$c_{0}=c_{1}=0$并递推即可

时间复杂度为$o(n)$，可以通过

 1 #include
 2 using namespace std;
 3 #define N 200005
 4 #define ll long long
 5 #define ld long double
 6 int n,bb[N],b[N],st[N];
 7 ll aa[N],a[N],c[N];
 8 ld ans;
 9 ld get_k(int x,int y){
10     return 1.0*(a[x]-a[y])/(x-y);
11 }
12 int main(){
13     scanf("%d",&n);
14     for(int i=1;i<=n;i++)scanf("%lld",&aa[i]);
15     for(int i=1;i<=n;i++)scanf("%d",&bb[i]);
16     for(int i=1;i<=n;i++)aa[0]=max(aa[0],aa[i]);
17     for(int i=1;i<=n;i++)
18         if (aa[i]==aa[0]){
19             for(int j=1;j<=n;j++){
20                 a[(j+n-i-1)%n+1]=aa[j];
21                 b[(j+n-i-1)%n+1]=bb[j];
22             }
23             break;
24         }
25     a[0]=a[n],c[0]=c[1]=0;
26     for(int i=2;i<=n;i++)c[i]=2*(b[i-1]+c[i-1])-c[i-2];
27     for(int i=0;i<=n;i++)a[i]-=c[i];
28     for(int i=0;i<=n;i++){
29         while ((st[0]>1)&&(get_k(st[st[0]-1],st[st[0]])0]-1],i)))st[0]--;
30         st[++st[0]]=i;
31     }
32     for(int i=1;i0];i++)
33         for(int j=st[i]+1;j<=st[i+1];j++)ans+=get_k(st[i],st[i+1])*(j-st[i])+a[st[i]]+c[j];
34     printf("%.10Lf\n",ans/n);
35     return 0;
36 }