首次架設靜態網站，如有疏失，還請多多包涵。歡迎來信zhuastor@gmail.com

解題心得

這題我花了大概一個小時多想，期間總共想了三種方法，然後吃了6個NA….，在時間複雜度方面還蠻不熟練的。
以下重點針對我AC的歷程解釋。

解題想法

時限0.5s，對於還不太會算自己code時間複雜度的人，這讓我蠻警戒的，所以我就先寫檢定時會做的穩定拿部分分的策略，用vector搭配pair存資料，然後找到一個能倒但是不用靠其他樹的樹，再來就依序往前一個”未倒”的樹判斷，然後這些可以倒的樹的資料就erase。
很顯然這方法光是刪除就會耗費大量時間。我的解法的重點就在於，快速找尋前一個或者後一個，所以必須想到一種方法可以不用用到刪除，我想到紀錄i樹的le[i]代表他前一個樹的位置，這樣就可以依賴陣列的性質，快速找尋前後依序”未倒”的樹。
提醒一下，我這邊維持的是左到右只掃一遍，這是解題的大方向，還請各位自己試試看。
然後為了方便我在前後各加入一組數據，分別是0及L。

AC code

#include<bits/stdc++.h>
using namespace std;
int n,l,num=0,maxd;
int c[100005];
int h[100005];
int le[100005];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n >>l;
    c[0]=h[0]=0;
    c[n+1]=h[n+1]=l;
    for(int x=1;x<=n;x++){cin >> c[x];le[x]=x-1;}
    for(int x=1;x<=n;x++)cin >> h[x];
    for(int x=1;x<=n;x++){
        if((c[x]-h[x]>=c[le[x]]) or (c[x]+h[x]<=c[x+1])){
            num++;
            le[x+1]=le[x];
            maxd=max(maxd,h[x]);
            while(true){
                if(le[x+1]>0 && c[le[x+1]]+h[le[x+1]]<=c[x+1]){
                    num++;
                    maxd=max(maxd,h[le[x+1]]);
                    le[x+1]=le[le[x+1]];
                    
                }
                else{
                    break;
                }
            }
        }
    }
    if(num==0){
        cout << 0 << endl;
        cout << 0 << endl;
    }
    else{
        cout << num << endl;
        cout << maxd << endl;
    }

    return 0;
}

題目連結 : 2020年1月APCS 3.砍樹