#38533: C++(23ms, 1.2MB)使用stack


bobobo0413 (杜拜、慕尼黑、蘇黎世、清邁、東京、首爾、布拉格)

學校 : 國立臺灣大學
編號 : 252359
來源 : [42.76.162.171]
最後登入時間 :
2024-04-13 18:42:54
h028. 202001_3 砍樹 -- 2020年1月APCS | From: [111.71.19.170] | 發表日期 : 2023-12-03 22:15

C++(23ms, 1.2MB)

解題想法:座標陣列設定c[0]=0;c[n+1]=l;然後從1遍歷到n檢查是否達到砍樹標準。接著是蠻重要的stack,中文是堆疊,也就是後進後出,常跟他對比的是佇列先進先出。使用stack的原因是因為由左到右檢查,基本上左界已經檢查好,剩下右界,所以越後面的要越先檢查。先設定堆疊的第一個是0,寫法是s.push(0),然後只要沒達砍樹標準就增加到堆疊,然後到下一顆樹再檢查是否有達砍樹標準,用s.top()取未砍樹的座標值。最後要取砍樹的最大高度,可用內建的max。

因為C和JAVA沒有很理解內建函式,所以只有用C++解這題,附上原始碼提供參考:

#include<bits/stdc++.h>
using namespace std;
#define e 1000000005
#define f 100005
int main()
{
int n,l,a=0,b,d=0;
scanf("%d%d",&n,&l);
int c[f],h[f],i,m;
stack<int> s;
c[0]=0;
c[n+1]=l;
h[0]=h[n+1]=e;
for(i=1;i<=n;i++)
    scanf("%d",&c[i]);
for(i=1;i<=n;i++)
    scanf("%d",&h[i]);
s.push(0);
for(i=1;i<=n;i++)
{
if((c[i]-h[i])>=c[s.top()]||(c[i]+h[i])<=c[i+1])
    {
        a++;
        d=max(d,h[i]);
            while(c[s.top()]+h[s.top()]<=c[i+1])
{
            a++;
        d=max(d,h[s.top()]);
      s.pop();
}
    }
    else
        s.push(i);
}
printf("%d\n%d\n",a,d);
    return 0;
}

 
ZeroJudge Forum