g277. 3. 幸運數字
Tags : APCS 分治法 區間最大值 笛卡爾樹 遞迴
Accepted rate : 826人/1251人 ( 66% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-09-06 18:13

Content

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

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

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

第一行輸入一個正整數 $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%) 無其他限制
Output

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

Sample Input #1
5
4 2 3 1 5
Sample Output #1
4
Sample Input #2
8
3 9 4 5 1 6 2 8
Sample Output #2
9
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (5%): 0.5s , <10M
公開 測資點#1 (5%): 0.5s , <10M
公開 測資點#2 (5%): 0.5s , <10M
公開 測資點#3 (5%): 0.5s , <10M
公開 測資點#4 (5%): 0.5s , <10M
公開 測資點#5 (5%): 0.5s , <10M
公開 測資點#6 (5%): 0.5s , <10M
公開 測資點#7 (5%): 0.5s , <10M
公開 測資點#8 (5%): 0.5s , <10M
公開 測資點#9 (5%): 0.5s , <10M
公開 測資點#10 (5%): 0.5s , <10M
公開 測資點#11 (5%): 0.5s , <10M
公開 測資點#12 (5%): 0.5s , <10M
公開 測資點#13 (5%): 0.5s , <10M
公開 測資點#14 (5%): 0.5s , <10M
公開 測資點#15 (5%): 0.5s , <10M
公開 測資點#16 (5%): 0.5s , <10M
公開 測資點#17 (5%): 0.5s , <10M
公開 測資點#18 (5%): 0.5s , <10M
公開 測資點#19 (5%): 0.5s , <10M
Hint :
Tags:
APCS 分治法 區間最大值 笛卡爾樹 遞迴
出處:
2021年9月APCS [管理者: cthbst (吳宗達) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
41237 glps1004@gma ... (Ian) g277
APCS202109全解析
221 2024-07-13 17:11
40454 qerpzzea@gma ... (賽希爾 cecill(陳宥穎)) g277
241 2024-05-21 20:17
34494 luray0601@gm ... (QWERTYPIG) g277
C++題解(含想法)
946 2023-03-26 12:34
33652 a110608@ctes ... (鍾均) g277
1006 2023-01-18 14:59
31815 arthur200511 ... (Arthur) g277
set/map/iterator
735 2022-08-21 12:00