D3: 進階演算法策略：分治法與貪心法則

在冥王星邊界的極端環境中，你需要快速做出最優決策。分治法和貪心法是兩種強大的演算法設計思想，能幫助你在複雜情況下找到高效解法。

分治法（Divide and Conquer）

核心思想：

1. 分解：將問題分成若干子問題
2. 解決：遞迴解決子問題
3. 合併：將子問題的解合併

經典範例：合併排序

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    return merge(left, right)

貪心法（Greedy Method）

核心思想：每一步都選擇當前最優解，期望得到全域最優解。 經典範例：活動選擇問題

def activity_selection(activities):
    # 按結束時間排序
    activities.sort(key=lambda x: x[1])
    
    selected = [activities[0]]
    for activity in activities[1:]:
        if activity[0] >= selected[-1][1]:
            selected.append(activity)
    
    return selected

範例 1：合併排序

import sys
def merge(left, right):
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    return merge(left, right)
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
sorted_arr = merge_sort(arr)
print(' '.join(map(str, sorted_arr)))

範例 2：找最大子陣列和

import sys
def max_subarray_sum(arr):
    """
    使用 Kadane's 演算法（貪心法）
    """
    max_sum = current_sum = arr[0]
    
    for num in arr[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    
    return max_sum
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
result = max_subarray_sum(arr)
print(f"最大子陣列和：{result}")

📝 Quiz：任務調度

給定 N 個任務，每個任務有開始時間和結束時間。選擇最多不重疊的任務。

輸入範例：

4
1 3
2 5
4 6
5 7

輸出：最多可執行 3 個任務

✅ Quiz 解答

import sys
def max_tasks(tasks):
    tasks.sort(key=lambda x: x[1])
    
    count = 1
    last_end = tasks[0][1]
    
    for start, end in tasks[1:]:
        if start >= last_end:
            count += 1
            last_end = end
    
    return count
n = int(sys.stdin.readline())
tasks = []
for _ in range(n):
    s, e = map(int, sys.stdin.readline().split())
    tasks.append((s, e))
result = max_tasks(tasks)
print(f"最多可執行 {result} 個任務")

🎯 APCS 對應能力

• 分治法：APCS 5 級分
• 貪心法：APCS 4-5 級分