在线编程介绍

阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：https://developer.aliyun.com/coding

本文为大家介绍其中的 第59题：期末考试 的题目解析，具体如下：

题目描述

题目等级：容易
知识点：概率

查看题目：期末考试
期末考试到了，n名标号1-n的同学坐成一排参加考试。考完试后，为了防止混乱，监考老师决定依次让第n个人的卷子传给第n-1个人，第n-1个人的卷子传给第n-2个人...第2个人的卷子传给第1个人，这样老师就能够直接收到所有人的卷子了。但是同学们经过了多年的考试，都练就了一身抄答案的好本领。再传卷子的过程中，第i个人都有ai概率抄到第i-1个人或者bi概率抄到第i+1个人。特殊的，a0与bn均为0。

但是每个人在抄他人的同时又不想被别人抄，被抓到了也得受罚。因此现在他们需要计算一下没有被抄到卷子的期望人数，以决定此次考试是否要大家一起作弊。
入参有四个，第一个是一个整数n，表示总人数。
第二个是一个整数m，表示被抓人数的上限。(1<= m <= n <= 10^5)。
第三个输入n个数，表示a1-an。
第四个输入n个数，表示b1-bn。
若此次被抄的期望人数不超过m，输出"Yes"，否则输出“No”。（不包括引号）

示例1
输入：
3
1
[0.000,0.500,0.500]
[0.500,0.500,0.000]
输出：
"No"

解题方法

根据题意，需要计算被抄的期望人数。那么首先要计算每个人被抄袭的概率。

第 i 个人可能被 i-1 抄，也有可能被 i+1 抄。被 i-1 抄的概率是 pre = b[i-1] ，被 i+1 抄的概率是 next = a[i+1] 。（若 i-1 或者 i+1 不存在，则被其抄的概率为 0 ）

在计算 i 被抄袭的概率时，可以先计算 i 不被抄袭的概率，再用 1 减去不被抄袭的概率即为被抄袭的概率。被抄袭的概率为：1-(1-pre)*(1-next)。

将每个同学被抄袭的概率相加，即可得到被抄袭的期望人数。

时间复杂度：O(n)
空间复杂度：O(1)
看完之后是不是有了想法了呢，快来练练手吧>>查看题目：期末考试