ZeroJudge 解題筆記：h206. 強者就是要戰，但......什麼才是強者呢？

作者：王一哲
日期：2025年11月11日


ZeroJudge 題目連結：h206. 強者就是要戰，但......什麼才是強者呢？

解題想法

這題考分治法。

Python 程式碼

使用時間約為 20 ms，記憶體約為 3.4 MB，通過測試。

def solve(nums, big):  # 自定函式，代入串列，是否取較大的值
    n = len(nums)  # 串列長度
    if n == 1: return nums[0]  # 遞迴出口，只剩一項，回傳此項
    left = nums[:n//2]  # 左半部
    right = nums[n//2:]  # 右半部
    mleft = solve(left, not big)  # 遞迴，代入左半部，big 的狀態要反過來
    mright = solve(right, not big)  # 遞迴，代入右半部，big 的狀態要反過來
    if big: return max(mleft, mright)  # 如果 big 為 True，取左、右兩半較大的值
    else: return min(mleft, mright)  # 反之，取左、右兩半較小的值

n = int(input())
arr = list(map(int, input().split()))
print(solve(arr, True))

C++ 程式碼

使用時間約為 3 ms，記憶體約為 288 kB，通過測試。

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

int solve(vector<int> nums, bool big) {
    if (nums.size() == 1) return nums[0];
    size_t m = nums.size();
    vector<int> left (nums.begin(), nums.begin() + m/2);
    vector<int> right (nums.begin() + m/2, nums.end());
    int mleft = solve(left, !big), mright = solve(right, !big);
    if (big) return max(mleft, mright);
    else return min(mleft, mright);
}

int main() {
    int n; scanf("%d", &n);
    vector<int> arr (n);
    for(int i=0; i<n; i++) scanf("%d", &arr[i]);
    printf("%d\n", solve(arr, true));
    return 0;
}