h206. 強者就是要戰,但......什麼才是強者呢?
標籤 : 遞迴
通過比率 : 127人/146人 ( 87% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-02-16 09:51

內容

強者的宿命就是要戰,找出強者的方法是這樣的:

 

假設現在有 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( 1 ≤ xi ≤ N ),
兩兩之間以空格隔開,代表每個人戰力值

輸出說明

最強者戰力值

範例輸入 #1
8
1 2 3 4 5 6 7 8
範例輸出 #1
6
測資資訊:
記憶體限制: 64 MB
提示 :

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

標籤:
遞迴
出處:
[管理者: mushroom.cs9 ... (mushroom) ]

本題狀況 本題討論 排行

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