1714 . 尋找蘿莉第二彈 - EX
TopCoder
Tags
Description
你，身為一個蘿莉控，身邊當然會有許多蘿莉，其中恰有一個蘿莉是SS級的蘿莉。你原本不知情，直到農曆新年放鞭炮時，SS 級的蘿莉因為被鞭炮嚇到而發出嬌柔的叫聲，你才發現他的存在。可惜當時你並沒有注意是哪隻蘿莉在叫，所以你為了要找出哪隻蘿莉是 SS 級的蘿莉而買了許多鞭炮。
為了省鞭炮，你將蘿莉們編號為 $0$ 到 $n-1$，依序從你的右邊開始往右排。每次放鞭炮時，你都可以控制音量，使得所有編號小於等於 $k$ 的蘿莉都聽到了鞭炮聲（$0 \leq k \leq n-1$），剩下的蘿莉都沒有聽到鞭炮聲。如果 SS 級的蘿莉聽到了鞭炮聲，你就會聽到那個令人精神振奮的叫聲；如果沒有，你就只會聽到鞭炮聲。你的目標是使用最少的鞭炮找出 SS 級的蘿莉。
另外，你其實早就調查了每個蘿莉是 SS 級的機率，並以陣列 $P[0],\cdots,P[n-1]$ 記錄，代表第 $i$ 隻蘿莉是 SS 級的機率是 $\dfrac{P[i]}{\sum_{j=0}^ {n-1}P[j]}$。請問，若你使用最佳的策略尋找 SS 級的蘿莉，所花費的鞭炮數的期望值 $X$ 是多少？
覺得似曾相識嗎？我也這麼覺得。但是你覺得我會那麼好心嗎？
Input Format
第一行有一個正整數 $n\leq 2\times 10^ 5$ 代表蘿莉的數量，
接著第二行會有 $n$ 個正整數，分別代表 $P[0],\cdots,P[n-1]$，其中 $P[i]\leq 10^ 9$。
| 子任務（測資） | 額外限制 | 分數 |
| 1 (0~1) | $P[i]=1$ | 5 |
| 2 (2~4) | $n\leq 18$ | 7 |
| 3 (2~7) | $n \leq 800$ | 10 |
| 4 (2~10) | $n \leq 4000$ | 13 |
| 5 (2~13) | $n \leq 10^ 4$ | 21 |
| 6 (0~19) | 無限制 | 44 |
Output Format
為了方便，請輸出 $X\times\sum_{i=0}^ {n-1}P[i] $。
Sample Input 1
2 1 1 1 1
Sample Output 1
Hints
對於範例測資的兩種解法：
一、先取$k=2$：
1. 如果聽到叫聲，就再取$k=0$：
1-1. 如果聽到叫聲，就找到了。
1-2. 如果沒有，取$k=1$就可以知道了。
2. 如果沒有，就再取$k=3$就可以知道了。
使用的鞭炮數的期望值是14/6。
二、也可以先取$k=0$：
1.如果聽到叫聲，就找到了。
2.如果沒有，就再取$k=2$：
2-1.如果聽到叫聲，就再取$k=1$就可以知道了。
2-2.如果沒有，就再取$k=3$就可以知道了。
使用的鞭炮數的期望值還是14/6。
Problem Source
Description by Paupière
Problem set by Yihda Yol
建國中學105學年度校內第五次模擬賽pC
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~1 | 5 |
| 2 | 2~4 | 7 |
| 3 | 2~7 | 10 |
| 4 | 2~10 | 13 |
| 5 | 2~13 | 21 |
| 6 | 0~19 | 44 |