h206. 強者就是要戰，但......什麼才是強者呢？

內容

強者的宿命就是要戰，找出強者的方法是這樣的：

假設現在有 N 人，我們可以分為左半邊 N/2 人和右半邊 N/2 人。
同樣地，對於左半邊 N/2 人，可以繼續平分為 N/4 人和 N/4 人，
直到無法再平分，也就是只剩下 1 人為止。

對於只有 1 人的區間，那人當然就是該區間內的最強者。
對於其他區間，則在找到左半邊最強者和右半邊最強者後，就可以簡單地對兩數字比較，以得到本身區間最強者。

但是強者的定義時常在變化，有時以小博大，有時以大搏小，兩者交替出現。
也就是假設這回合大者優先，則下回合會是小者優先，下下回合則又回到大者優先，依序下去......

這邊我們預設最初 N 人的區間為大者優先，
因此所劃分出的 N/2, N/2 區間將為小者優先，繼續劃分出的 N/4, N/4, N/4, N/4 則又回到大者優先......

給定 N 值和由左至右相異的 N 人戰力值，
依照上述比較方法，請問最強者戰力值會是多少？

舉例來說，
當 N = 8，戰力值由左至右依序為 {1, 2, 3, 4, 5, 6, 7, 8}，則所找出的最強者將為 6。
下圖為尋找過程，其中區間紅框表示該區間為大者優先，反之則為小者優先：

輸入說明

第一行有一個正整數 N，
代表總共有 N 人 ( 1 ≤ N ≤ 1024 )，其中 N 必為 2 的整數次方

第二行由左至右有 N 個相異正整數 x_i( 1 ≤ x_i ≤ N )，
兩兩之間以空格隔開，代表每個人戰力值

輸出說明

最強者戰力值

範例輸入 #1

8
1 2 3 4 5 6 7 8

範例輸出 #1

測資資訊：

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

提示：

你可以定義類似下面的函式：
int findMax(int l, int r, int x[], bool bigFirst)以找出 x[l:r] 區間內最強者，其中 bigFirst 代表對於該區間是否大者優先。

標籤:

遞迴

出處:

[管理者： mushroom.cs9 ... (mushroom) ]

編號	身分	題目	主題	人氣	發表日期
39313	toseanlin@gm ... (Dr. SeanXD)	h206	解題思路	194	2024-02-05 01:27
39116	sophie198205 ... (闕河正)	h206	解題報告	171	2024-01-15 21:18