h071. 202109_3. 幸運數字（測資增強版）

內容

在 $n$ 個人之中，每個人被分配到一個號碼，記錄為 $a_{1}, a_{2}, \dots, a_{n}$ ，這些號碼彼此都不相同，我們要找出當中最幸運的一個
已知在 $[L, R]$ 區間之中，最幸運號碼定義為：

當 $L = R$ 時，幸運號碼為 $a [L]$
當 $L < R$ 時，找出當中最小號碼的位置 $m$ ，並以最小號碼所在的位置將整個區間區分為左邊 $[L, m - 1]$ 與右邊 $[m + 1, R]$ ，計算兩個區間各自的總和，總和比較大的區間即為幸運號碼所在的區間；如果兩個區間的總和相等，則幸運號碼位在右邊的區間，若區間不包含任何數字，總和視為 $0$

重複以上步驟直到收斂至1. 時即可找到幸運號碼
請找出這 $n$ 個人之中的幸運號碼

P.S 本題題敘來自演算法海牛，但因官方測驗中以worst case 為 $O (n^{2})$ 的程式會拿到 0 分，因此補上（或許）更貼近官方的測資供大家練習

輸入說明

第一行輸入一個正整數 $n (1 \leq n \leq 3 \times 10^{5})$ ，接下來有 $n$ 個數字 $a_{1}, a_{2}, \dots, a_{n} (1 \leq a_{i} \leq 10^{7})$

配分

(50%) $1 \leq a_{i} \leq n$ ，所有數字都介於 $1 \sim n$
(50%) 無其他限制

輸出說明

輸出這 $n$ 個數字中的幸運數字數值

範例輸入 #1

5
4 2 3 1 5

範例輸出 #1

範例輸入 #2

8
3 9 4 5 1 6 2 8

範例輸出 #2

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (5%): 1.0s , <10M
公開測資點#1 (5%): 1.0s , <10M
公開測資點#2 (5%): 1.0s , <10M
公開測資點#3 (5%): 1.0s , <10M
公開測資點#4 (5%): 1.0s , <10M
公開測資點#5 (5%): 1.0s , <10M
公開測資點#6 (5%): 1.0s , <10M
公開測資點#7 (5%): 1.0s , <10M
公開測資點#8 (5%): 1.0s , <10M
公開測資點#9 (5%): 1.0s , <10M
公開測資點#10 (5%): 1.0s , <10M
公開測資點#11 (5%): 1.0s , <10M
公開測資點#12 (5%): 1.0s , <10M
公開測資點#13 (5%): 1.0s , <10M
公開測資點#14 (5%): 1.0s , <10M
公開測資點#15 (5%): 1.0s , <10M
公開測資點#16 (5%): 1.0s , <10M
公開測資點#17 (5%): 1.0s , <10M
公開測資點#18 (5%): 1.0s , <10M
公開測資點#19 (5%): 1.0s , <10M

提示：

標籤:

APCS

出處:

2021年9月 APCS [管理者： ktlai@cmgsh.tp.edu.tw

ktlai@cmgsh. ... (賴楷宗) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」