ZeroJudge 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。
下圖為尋找過程，其中區間紅框表示該區間為大者優先，反之則為小者優先。

ZeroJudge H206 題目舉例圖文說明

範例測資

範例輸入範例輸出
第一行有一個正整數 N，
代表總共有 N 人 ( 1 ≤ N ≤ 1024 )，其中 N 必為 2 的整數次方。
第二行由左至右有 N 個相異正整數 xi ( 1 ≤ xi ≤ N )，兩兩之間以空格隔開，代表每個人戰力值。		最強者戰力值
8
1 2 3 4 5 6 7 8		6

解題思路

使用遞迴的方式將數量一直切成一半，當數列只剩下一個數字時 (左界線＝右界線)，就 return 目前的數字。大小的判斷可以每次進入函式時將一個布林值反轉並且 return 最大值或最小值。

範例程式碼－ZeroJudge H206: 強者就是要戰，但……什麼才是強者呢？

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int>num;

int findMax (int l, int r, bool bigFirst)
{
    if (l == r)
    {
        return num[l];
    }
    if (bigFirst)
    {
        int hi = max(findMax(l, (l+r)/2, false), findMax(((l+r)/2)+1, r, false));
        return hi;
    }
    int hi = min(findMax(l, (l+r)/2, true), findMax(((l+r)/2)+1, r, true));
    return hi;
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    for (int i = 0; i<N; i++)
    {
        int tmp;
        cin >> tmp;
        num.push_back(tmp);
    }
    cout << findMax(0, int(num.size())-1, true) << "\n";
}

//ZeroJudge H206
//Dr. SeanXD
標籤

相關文章

發佈留言