信阳网站开发建设公司,广东十大网站建设,大青海网app,flash教程自学网最开始我们先旋转一下这张桌子#xff0c;使得 A1An1max{Ai}A_1A_{n1}\max\{A_i\}A1An1max{Ai}。
这是非常有效的#xff0c;因为我们把环就变成链#xff0c;只要到达了链的任意一端 1/n11/n11/n1 就肯定会结束游戏。
定义 Ei:E_i:Ei: 从 iii 开始游戏#xf…最开始我们先旋转一下这张桌子使得 A1An1max{Ai}A_1A_{n1}\max\{A_i\}A1An1max{Ai}。
这是非常有效的因为我们把环就变成链只要到达了链的任意一端 1/n11/n11/n1 就肯定会结束游戏。
定义 Ei:E_i:Ei: 从 iii 开始游戏运用最优策略结束游戏的期望收益。
显然E1A1,En1An1,∀1≤i≤nEimax(Ai,Ei−1Ei12−Bi)E_1A_1,E_{n1}A_{n1},\forall_{1\le i\le n}E_{i}\max\Big(A_{i},\frac{E_{i-1}E_{i1}}2-B_i\Big)E1A1,En1An1,∀1≤i≤nEimax(Ai,2Ei−1Ei1−Bi)。 简化问题假设没有这个 BiB_iBi 存在。
把 iii 看成 (i,Ai)(i,A_i)(i,Ai) 放到二维平面内则答案 EiE_iEi 就是 iii 为横坐标时在这些点维护出的凸壳上的纵坐标。
画画图就知道了。
维护凸壳以及求解答案是可以在线性时间内完成的。 考虑将当前复杂问题往简单问题上靠拢。
能否构造出一个新形式的 FiF_iFi 将 BiB_iBi 抵消掉即 Fimax(Gi,Fi−1Fi12)F_i\max\Big(G_i,\frac{F_{i-1}F_{i1}}2\Big)Fimax(Gi,2Fi−1Fi1)再通过 FiF_iFi 反推回 EiE_iEi。
Ei−Cimax(Ai−Ci,Ei−1Ei12−Ci−Bi)⇕E_i-C_i\max\Big(A_i-C_i,\frac{E_{i-1}E_{i1}}2-C_i-B_i\Big)\\ \UpdownarrowEi−Cimax(Ai−Ci,2Ei−1Ei1−Ci−Bi)⇕Ei−Cimax(Ai−Ci,Ei−1−Ci−1Ei1−Ci12Ci−1Ci12−Ci−Bi)E_i-C_i\max\Big(A_i-C_i,\frac{E_{i-1}-C_{i-1}E_{i1}-C_{i1}}2\frac{C_{i-1}C_{i1}}2-C_i-B_i\Big)Ei−Cimax(Ai−Ci,2Ei−1−Ci−1Ei1−Ci12Ci−1Ci1−Ci−Bi)
因为 BiB_iBi 是常量前面的系数是不带 iii 的任一次方的所以我们构造的时候应该先考虑不出现带 iii 系数的形式
发现只要令 ∀1≤i≤nCi−1Ci12−Ci−Bi0\forall_{1\le i\le n}\frac{C_{i-1}C_{i1}}2-C_i-B_i0∀1≤i≤n2Ci−1Ci1−Ci−Bi0 就能达到目的。
⇒Ci−Ci−12BiCi1−Ci\Rightarrow C_i-C_{i-1}2B_iC_{i1}-C_i⇒Ci−Ci−12BiCi1−Ci 且 C2C10C_2C_10C2C10这样 CCC 就递推出来了。
令 FiEi−CiF_iE_i-C_iFiEi−Ci则 Fimax(Ai−Ci,Fi−1Fi12)F_i\max\Big(A_i-C_i,\frac{F_{i-1}F_{i1}}2\Big)Fimax(Ai−Ci,2Fi−1Fi1)以 (i,Fi)(i,F_i)(i,Fi) 构造凸壳即可线性求解。
先维护出凸壳后再挨个求纵坐标。
#include bits/stdc.h
using namespace std;
#define int long long
#define double long double
#define maxn 200005
int A[maxn], B[maxn], C[maxn], s[maxn];
double ans;
int n;signed main() {scanf( %lld, n );for( int i 1;i n;i ) scanf( %lld, A[i] );for( int i 1;i n;i ) scanf( %lld, B[i] );int id max_element( A 1, A n 1 ) - A;rotate( A 1, A id, A n 1 );rotate( B 1, B id, B n 1 );A[n 1] A[1], B[n 1] B[1];for( int i 3;i n 1;i ) C[i] ( B[i - 1] C[i - 1] 1 ) - C[i - 2];for( int i 1;i n 1;i ) A[i] - C[i];int top 0;s[ top] 1;for( int i 2;i n 1;i ) {while( top and (A[i] - A[s[top]]) * (s[top] - s[top - 1]) (A[s[top]] - A[s[top - 1]]) * (i - s[top]) ) top --;/*( A[i]-A[s[top]] ) / ( i-s[top] ) k1 of new line( A[s[top]]-A[s[top-1]] ) / ( s[top]-s[top-1]) k1 of latest lineif k1k2 throw k2*/s[ top] i;}double ans 0;top 0;for( int i 1;i n;i ) {if( s[top 1] i ) top ;ans (A[s[top 1]] - A[s[top]]) * 1.0 / (s[top 1] - s[top] ) * (i - s[top]) A[s[top]];//将凸包上的一条边抽变成从原点开始计算ans C[i];}printf( %.12Lf\n, ans / n );return 0;
}
