Codeforces 558A Lala Land and Apple Trees：貪心雙指針採摘蘋果

問題描述

數軸上有蘋果樹，位置 x_i，蘋果數 a_i。從原點出發，每次只能向左或向右走到最近的未採摘樹，採摘後繼續交替方向。求最大可採摘蘋果總數。n ≤ 100。

關鍵洞察

最優策略必然是：先向某一方向（左/右）走到最近的樹，然後交替。因為跳過更近的樹去採摘更遠的樹永遠不劣（反而會錯過中間的樹）。因此只需考慮兩種起始方向：先左後右、先右後左。

算法步驟

1. 將樹按位置分為左邊（負）和右邊（正），各自按距離原點絕對值升序排序。
2. 模擬兩種策略：
   • 策略 A：左、右、左、右……
   • 策略 B：右、左、右、左……
3. 取兩者最大值。

代碼實現

struct Tree { int x, a; } L[105], R[105];
int main() {
    int n; while (scanf("%d",&n)==1) {
        int lc=0, rc=0;
        for (int i=0;i=lc) break; ans1+=L[i++].a; }
            else { if (j>=rc) break; ans1+=R[j++].a; }
        }
        // 策略 B：先右
        for (int i=0,j=0,k=0; ; k++) {
            if (k%2==0) { if (j>=rc) break; ans2+=R[j++].a; }
            else { if (i>=lc) break; ans2+=L[i++].a; }
        }
        printf("%d\n", max(ans1, ans2));
    }
    return 0;
}

複雜度

排序 O(n log n)，模擬 O(n)，極快。

總結

CF 558A 是典型的「貪心 + 雙指針模擬」題。關鍵在於證明「交替採摘最近樹」的最優性，並正確處理左右兩側樹數量不等導致的提前結束。代碼簡短，思維清晰，是入門貪心題的佳例。