A7097. 列队春游
编程题
普及+/提高
知识点
题目描述
给定正整数数列 $h_1,h_2,\cdots,h_n$。设 $p$ 为 $1\sim n$ 的随机排列。
定义 $h'_i=h_{p_i}$。定义 $\mathrm{pre}_i$ 为最大的 $j\lt i$ 满足 $h'_j\ge h'_i$（如果不存在，规定为 $0$）。
求出 $\displaystyle \sum_{i=1}^n (i-\mathrm{pre}_i)$ 的期望值，保留两位小数输出。
定义 $h'_i=h_{p_i}$。定义 $\mathrm{pre}_i$ 为最大的 $j\lt i$ 满足 $h'_j\ge h'_i$（如果不存在，规定为 $0$）。
求出 $\displaystyle \sum_{i=1}^n (i-\mathrm{pre}_i)$ 的期望值，保留两位小数输出。
输入格式
第一行一个正整数 $n$，表示数列长度。
第二行 $n$ 个正整数 $h_i$。
第二行 $n$ 个正整数 $h_i$。
输出格式
输出一行一个实数，表示答案，保留两位小数。
输入输出样例
输入 #1
3 3 2 1
输出 #1
4.33
说明/提示
## 数据范围
对于 $20\%$ 的数据，$1\leq n\leq 10$；
对于 $50\%$ 的数据，$1\leq n\leq 70$，且 $h_i$ 互不相同；
对于 $100\%$ 的数据，保证 $1\leq n\leq 300$，$1\leq h_i\leq 1000$。
对于 $20\%$ 的数据，$1\leq n\leq 10$；
对于 $50\%$ 的数据，$1\leq n\leq 70$，且 $h_i$ 互不相同；
对于 $100\%$ 的数据，保证 $1\leq n\leq 300$，$1\leq h_i\leq 1000$。