济南机关建设网站,页网站设计,沈阳seo关键词排名优化软件,一个服务器可以建多少个网站2023河南萌新联赛第#xff08;六#xff09;场#xff1a;河南理工大学-F 爱睡大觉的小C
https://ac.nowcoder.com/acm/contest/63602/F 文章目录 2023河南萌新联赛第#xff08;六#xff09;场#xff1a;河南理工大学-F 爱睡大觉的小C题意解题思路 题意
新学期的概…2023河南萌新联赛第六场河南理工大学-F 爱睡大觉的小C
https://ac.nowcoder.com/acm/contest/63602/F 文章目录 2023河南萌新联赛第六场河南理工大学-F 爱睡大觉的小C题意解题思路 题意
新学期的概率论课上小C正在睡大觉然而概率论老师的讲课声音还是传到了小C的梦里… 原本小C正在梦中享受打败小Y的胜利突然小C面前出现了一个长度为 n ( 1 ≤ n ≤ 2 × 1 0 5 ) n(1\le n\le 2\times 10^5) n(1≤n≤2×105)的数组 a 1 , a 2 , a 3 , . . . a n ( 1 ≤ a i ≤ 1 0 7 ) a_1,a_2,a_3,...a_n(1\le a_i\le 10^7) a1,a2,a3,...an(1≤ai≤107) ,然后概率论老师的声音飘入了他的梦境“这第 k k k个较大的数的期望是…”,于是小C便想求出对于所有长度大于等于 k ( 1 ≤ k ≤ 100 ) k(1\le k\le 100) k(1≤k≤100)的连续子区间中第 k k k大的数的期望是多少。请你帮小C计算出来。 文本解释 连续子区间对于一个数组它的连续子区间可以由删掉头和尾的0个或多个数字得到例如 a [ 1 , 4 , 2 , 6 , 5 ] a[1,4,2,6,5] a[1,4,2,6,5]则集合 [ 1 , 4 , 2 ] , [ 4 , 2 , 6 ] [1,4,2],[4,2,6] [1,4,2],[4,2,6]都是集合 a a a的连续子区间而集合 [ 1 , 2 , 6 ] [1,2,6] [1,2,6]则不是因为跳过 a 2 4 a_24 a24不连续了 第 k k k大的数一个数组中有最大的数,次大的数,…,第个 k k k大的数。 例如 a [ [ 114514 , 1557 , 2333 , 666 , 369 ] a[[114514,1557,2333,666,369] a[[114514,1557,2333,666,369]显然第一大的数是 114514 ] 114514] 114514]第二大的数是 2333 2333 2333。 期望在概率论和统计学中数学期望或均值亦简称期望是试验中每次可能结果的概率乘以其结果的总和
解题思路
看题面 1 ≤ k ≤ 100 1\le k\le 100 1≤k≤100尤其引人注目必有大用。可以发现小于其的数对其是否为区间第 k k k大没有影响我们可以使用链表按照数值将 { a } \{a\} {a}排序从小到大枚举每处理完一个数就将它从链表中删除对于某个数 x x x大于其的数都在链表中而小于其的数都被删去。在其中找到最前的包含 x x x使 x x x为第 k k k大的 l l l让 l l l通过链表直到 x x x在此过程中求取各个合法的期望值可以达到 O ( n k ) O(nk) O(nk)的复杂度。注意处理边界情况。 ##代码
#includebits/stdc.h
using namespace std;
const int N2e55;
struct link{int lf,rf;
}b[N];
struct node{int x,id;
}c[N];
int a[N],n,k;
long long dp[N];
bool cmp(node a,node b){return a.xb.x;
}
void Delete(int x){b[b[x].lf].rfb[x].rf;b[b[x].rf].lfb[x].lf;
}
int main(){cinnk;for(int i1;in;i){cina[i];c[i].xa[i];c[i].idi;b[i].lfi-1,b[i].rfi1;}b[n1].rfn1;sort(c1,cn1,cmp);for(int i1;in;i){int xc[i].id;int lx;int j;for(j1;jkb[l].lf!0;j)lb[l].lf;int Lb[l].lf;int rx;for(;jkb[r].rf!n1;j)rb[r].rf;if(jk){Delete(x);continue;}int Rb[r].rf;while(L!xr!n1){dp[x]1ll*(l-L)*(R-r);lL,Lb[L].lf;rR,Rb[R].rf;}Delete(x);}long long sum0;for(int i1;in;i)sumdp[i];double ans0;for(int i1;in;i)ans1ll*a[i]*dp[i]*1.0/sum;printf(%.2lf,ans);
}
