發表新討論
#28863: 剩下40%TLE了...


s0975247623@gmail.com (愛吃又愛睡的Weber)

學校 : 高雄市立高雄高級中學
編號 : 136210
來源 : [42.77.23.117]
最後登入時間 ：
2023-01-17 20:53:17
h028. 202001_3 砍樹 -- 2020年1月APCS | From: [223.139.5.112] | 發表日期 : 2022-01-09 00:50

最後40%速度卡住，不得不說這時間複雜度其實真的不怎麼樂觀，但我也想不出更快的了

我的想法是不停的掃，一發現有棵樹有足夠空間倒下，就用link list跨過那棵樹，當找不到樹可砍時found = false，跳出while迴圈

有沒有大神有更好的做法...

#include <iostream>
#define ll long long
using namespace std;
ll cnt = 0, highest = 0, pos[100005], hight[100005],edge[100005][2], n, l;
bool cut[100005] = {false};
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> l;
    for (int i = 1; i <= n; ++i)
    {
        cin >> pos[i];
    }
    pos[0] = 0;
    pos[n + 1] = l;
    for (int i = 1; i <= n; ++i)
    {
        cin >> hight[i];
    }
    edge[0][1] = 1;
    edge[n + 1][0] = n;
    for (int i = 1; i <= n; ++i)
    {
        edge[i][0] = i - 1;
        edge[i][1] = i + 1;
    }
    while (true)
    {
        bool found = false;
        for (int i = 1; i <= n; ++i)
        {
            if (!cut[i])
            {
                if ((pos[i] - hight[i] >= pos[edge[i][0]]) || (pos[i] + hight[i] <= pos[edge[i][1]]))
                {
                    ++cnt;
                    edge[edge[i][0]][1] = edge[i][1];
                    edge[edge[i][1]][0] = edge[i][0];
                    highest = max(highest, hight[i]);
                    cut[i] = true;
                    found = true;
                }
            }
        }
        if (!found)
            break;
    }
    cout << cnt << endl << highest;
    return 0;
}
 
#28898: Re:剩下40%TLE了...


cges30901 (cges30901)

學校 : 不指定學校
編號 : 30877
來源 : [101.136.203.77]
最後登入時間 ：
2024-04-07 15:34:14
h028. 202001_3 砍樹 -- 2020年1月APCS | From: [39.10.69.93] | 發表日期 : 2022-01-10 20:01

最後40%速度卡住，不得不說這時間複雜度其實真的不怎麼樂觀，但我也想不出更快的了

我的想法是不停的掃，一發現有棵樹有足夠空間倒下，就用link list跨過那棵樹，當找不到樹可砍時found = false，跳出while迴圈

有沒有大神有更好的做法...

#include
#define ll long long
using namespace std;
ll cnt = 0, highest = 0, pos[100005], hight[100005],edge[100005][2], n, l;
bool cut[100005] = {false};
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> l;
    for (int i = 1; i <= n; ++i)
    {
        cin >> pos[i];
    }
    pos[0] = 0;
    pos[n + 1] = l;
    for (int i = 1; i <= n; ++i)
    {
        cin >> hight[i];
    }
    edge[0][1] = 1;
    edge[n + 1][0] = n;
    for (int i = 1; i <= n; ++i)
    {
        edge[i][0] = i - 1;
        edge[i][1] = i + 1;
    }
    while (true)
    {
        bool found = false;
        for (int i = 1; i <= n; ++i)
        {
            if (!cut[i])
            {
                if ((pos[i] - hight[i] >= pos[edge[i][0]]) || (pos[i] + hight[i] <= pos[edge[i][1]]))
                {
                    ++cnt;
                    edge[edge[i][0]][1] = edge[i][1];
                    edge[edge[i][1]][0] = edge[i][0];
                    highest = max(highest, hight[i]);
                    cut[i] = true;
                    found = true;
                }
            }
        }
        if (!found)
            break;
    }
    cout << cnt << endl << highest;
    return 0;
}

 

改了很久終於AC了......分享一下我的作法：
1. 不需要不停的掃，只要從最左邊向右檢查，如果有空間倒下，再往回檢查左邊那棵樹

2. for迴圈不要用++i，這裡不改你的程式一樣40% TLE，改成i=edge[i][1]會快很多（我想超久才把這裡改掉）

 
#28951: Re:剩下40%TLE了...


s0975247623@gmail.com (愛吃又愛睡的Weber)

學校 : 高雄市立高雄高級中學
編號 : 136210
來源 : [42.77.23.117]
最後登入時間 ：
2023-01-17 20:53:17
h028. 202001_3 砍樹 -- 2020年1月APCS | From: [42.75.197.203] | 發表日期 : 2022-01-15 14:17

最後40%速度卡住，不得不說這時間複雜度其實真的不怎麼樂觀，但我也想不出更快的了

我的想法是不停的掃，一發現有棵樹有足夠空間倒下，就用link list跨過那棵樹，當找不到樹可砍時found = false，跳出while迴圈

有沒有大神有更好的做法...

#include
#define ll long long
using namespace std;
ll cnt = 0, highest = 0, pos[100005], hight[100005],edge[100005][2], n, l;
bool cut[100005] = {false};
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> l;
    for (int i = 1; i <= n; ++i)
    {
        cin >> pos[i];
    }
    pos[0] = 0;
    pos[n + 1] = l;
    for (int i = 1; i <= n; ++i)
    {
        cin >> hight[i];
    }
    edge[0][1] = 1;
    edge[n + 1][0] = n;
    for (int i = 1; i <= n; ++i)
    {
        edge[i][0] = i - 1;
        edge[i][1] = i + 1;
    }
    while (true)
    {
        bool found = false;
        for (int i = 1; i <= n; ++i)
        {
            if (!cut[i])
            {
                if ((pos[i] - hight[i] >= pos[edge[i][0]]) || (pos[i] + hight[i] <= pos[edge[i][1]]))
                {
                    ++cnt;
                    edge[edge[i][0]][1] = edge[i][1];
                    edge[edge[i][1]][0] = edge[i][0];
                    highest = max(highest, hight[i]);
                    cut[i] = true;
                    found = true;
                }
            }
        }
        if (!found)
            break;
    }
    cout << cnt << endl << highest;
    return 0;
}

 

改了很久終於AC了......分享一下我的作法：
1. 不需要不停的掃，只要從最左邊向右檢查，如果有空間倒下，再往回檢查左邊那棵樹

2. for迴圈不要用++i，這裡不改你的程式一樣40% TLE，改成i=edge[i][1]會快很多（我想超久才把這裡改掉）


已AC，超級感謝

 
ZeroJudge Forum