某音樂平台正在測試一套新的智慧隨機播放系統。
系統有一份長度為 $n$ 的播放清單，第 $i$ 首歌具有一個人氣權重 $w_i$，權重越高，歌曲被播放到的機率就越高。
為了增加多樣性，系統在每次播放時不一定會考慮整個清單，而只會從某一段區間 $(l \; , \; r)$ 的歌曲中挑選。
在這段區間內，歌曲會依照權重比例被選中。
設這段區間的總權重為 $S = \sum_{i=l}^{r} w_i$ 。
系統會產生一個隨機比例 $\frac{a}{a+b}$ 。
播放器會從左到右累積歌曲權重，當累積比例第一次不小於這個隨機比例時，就選擇該歌曲播放。
也就是說，需要找到一個位置 $k$ 滿足 $\frac{\sum_{i=l}^{k-1} w_i}{S} \le \frac{a}{a+b} \le \frac{\sum_{i=l}^{k} w_i}{S}$
請你幫系統找出會被播放的歌曲位置 $k$ 。
第一列輸入兩數 $n,m$ 代表數列長度和詢問次數。
第二列輸入 $n$ 個 $w_i$ 代表人氣權重。
接下來 $m$ 列輸入 $l \; , \; r \; , \; a \; , \; b$ 分別代表左界、右界、產生比例的值。
輸出符合需求的第 $k$ 項。
範例一: 5 1 2 3 5 4 6 1 5 1 1 ------ 範例二: 6 3 2 1 3 4 2 5 1 6 1 1 1 4 1 3 4 6 2 1
範例一: 3 ------ 範例二: 4 2 6
$40\;\% : 1\leq n , m \leq 10^{3} \; , \; 1 \leq w_i \leq 10^{4} \; , \; 1 \leq l , r \leq n \; , \; 1 \leq a , b \leq 10$
$60\;\% : 1\leq n , m \leq 10^{5} \; , \; 1 \leq w_i \leq 10^{4} \; , \; 1 \leq l , r \leq n \; , \; 1 \leq a , b \leq 10$
範例一:
區間總和 $= \sum_{i=l}^{r} w_i = 20$ ，比例 $= \frac{a}{a+b} = \frac{1}{2}$ ，門檻 $= 20 \times \frac{1}{2} = 10$ 。
累計權重 $= 2 \; , \; 5 \; , \; 10 \; , \; 14 \; , \; 20$ 。
因為 $ 5\leq 10 \leq 10$ ，所以 $ k = 3$ 。
------
範例二:
$query \; 1:$
區間總和 $= \sum_{i=l}^{r} w_i = 17$ ，比例 $= \frac{a}{a+b} = \frac{1}{2}$ ，門檻 $= 17 \times \frac{1}{2} = 8.5$ 。
累計權重 $= 2 \; , \; 3 \; , \; 6 \; , \; 10 \; , \; 12 \; , \; 17$ 。
因為 $ 6\leq 8.5 \leq 10$ ，所以 $ k = 4$ 。
$query \; 2:$
區間總和 $= \sum_{i=l}^{r} w_i = 10$ ，比例 $= \frac{a}{a+b} = \frac{1}{4}$ ，門檻 $= 10 \times \frac{1}{4} = 2.5$ 。
累計權重 $= 2 \; , \; 3 \; , \; 6 \; , \; 10$ 。
因為 $ 2\leq 2.5 \leq 3$ ，所以 $ k = 2$ 。
$query \; 3:$
區間總和 $= \sum_{i=l}^{r} w_i = 11$ ，比例 $= \frac{a}{a+b} = \frac{2}{3}$ ，門檻 $= 10 \times \frac{2}{3} \approx 7.33$ 。
累計權重 $= 4 \; , \; 6 \; , \; 11$ 。
因為 $ 4\leq 7.33 \leq 11$ ，所以 $ k = 6$ 。
肯定不是APCS。
題解。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||