算法筆試模拟題精解之“期末考試”

線上程式設計介紹

阿裡雲開發者社群線上程式設計産品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費線上刷題神器。題庫來自筆試模拟題、算法大賽模拟題等，界面整潔明了，操作簡單，為使用者營造專心答題的學習環境。點選連結開始體驗：

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)

看完之後是不是有了想法了呢，快來練練手吧>>