APCS202109 第3題幸運數字

在 n 個人之中，每個人被分配到一個號碼，記錄為 a1,a2,…,an，這些號碼彼此都不相同，我們要找出當中最幸運的一個

已知在[L,R] 區間之中，最幸運號碼定義為：

當 L=R 時，幸運號碼為 a[L]

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

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

輸入說明

第一行輸入一個正整數 n(1≤n≤3×10^5)，接下來有 n 個數字 a1,a2,…,an(1≤ai≤10^7)

輸出說明

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

輸入範例

5

4 2 3 1 5

8

3 9 4 5 1 6 2 8

輸出範例

4

9

解題策略

前綴和、遞迴、map

使用map建立數字與索引值對應的字典，且鍵值由小到大排序，可以加速搜尋每個區間最小數值所在位置。