算法題：彩虹橋跳躍求和——逆向貪心 O(N) 解法

題目：兔子從第 1 格開始，每次在剩餘格子中跳往**美觀度最大**的格子（相同取前者），直到第 N 格，求經過格子美觀度之和。N 最大 200,000，需 O(N) 或 O(N log N) 算法。

樣例解析

• 輸入：`5 9 4 6 10 8 7 5 4 7` (N=10)
• 路徑：1(5) → 5(10) → 6(8) → 7(7) → 10(7) = 37

核心洞察：逆向思維 + 單調棧/最大值追蹤

正向模擬需反覆掃描「當前位置到末尾」的最大值，最壞 O(N²)。**關鍵觀察**：最終被訪問的格子序列，其美觀度**單調不增**（每次跳到剩餘最大值，後續最大值不可能比當前大）。

因此可從**右向左**掃描，維護「當前遇到的最大值」：

• 初始 `maxVal = a[N-1]`（最後一格必被訪問），`sum = maxVal`。
• 從 `N-2` 遞減到 `0`：
• 若 `a[i] > maxVal`：說明這是新的「局部最大值」，兔子會跳到這裡。累加 `sum += a[i]`，更新 `maxVal = a[i]`。
• 若 `a[i] <= maxVal`：兔子不會停在這裡（後面有更大或相同且更前的值），跳過。

算法正確性證明

兔子策略等價於：選取序列中**從左到右的「嚴格遞增峰值」**（包含首元素）。逆向掃描正是在提取這些峰值。因為若某元素不是峰值，其右側必有 ≥ 它的元素，兔子會直接跳過它。

C++ 實現 (O(N) 時間, O(1) 空間)

#include 
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    if (!(cin >> N)) return 0;
    vector a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    
    long long sum = a[N-1];
    long long curMax = a[N-1];
    
    for (int i = N - 2; i >= 0; --i) {
        if (a[i] > curMax) {
            curMax = a[i];
            sum += curMax;
        }
    }
    cout << sum << "\n";
    return 0;
}

Java 實現

import java.util.Scanner;

public class RainbowBridge {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        long[] a = new long[N];
        for (int i = 0; i < N; i++) a[i] = sc.nextLong();
        
        long sum = a[N-1];
        long curMax = a[N-1];
        
        for (int i = N-2; i >= 0; i--) {
            if (a[i] > curMax) {
                curMax = a[i];
                sum += curMax;
            }
        }
        System.out.println(sum);
    }
}

複雜度與邊界

• 時間：O(N)，單次掃描。
• 空間：O(1) 額外空間（不計輸入數組）。
• 數據類型：美觀度之和可能超過 32 位整數，務必用 `long long` / `long`。
• N=1 時直接輸出該值（迴圈不執行）。

這一逆向貪心策略完美解決大規模數據下的彩虹橋問題。