發表新討論
#29995: 請問為何到第五筆測資就TLE了


s111010137@student.nqu.edu.tw (Khazix)

學校 : 國立金門大學
編號 : 177202
來源 : [1.172.139.67]
最後登入時間 ：
2022-11-09 22:20:56
f607. 3. 切割費用 -- 2021年1月APCS | From: [39.10.161.177] | 發表日期 : 2022-04-19 23:02

#include <iostream>

#include <iomanip>

#include <algorithm>

using namespace std;

int num[200001] = { 0 };

int address[200001] = { 0 };

void Sort(int n, int num[], int address[]);

int main(void)

{

    cin.tie(0);

    std::ios::sync_with_stdio(false);

 

    int n, l;

 

    while (cin >> n >> l)

    {

        long long int sum = 0;

 

        for (int i = 0; i < n; i++)

        {

            cin >> num[i] >> address[i];

        }

 

        Sort(n, num, address);

 

        for (int i = 0; i < n; i++)

        {

            int min_left = num[i] - 0;

            int min_right = l - num[i];

 

            for (int j = 0; j < i; j++)

            {

                // 找到低於 num[i] 並且離 num[i] 最近的

 

                if ((num[i] - num[j]) > 0 && num[i] - num[j] < min_left)

                {

                    min_left = num[i] - num[j];

                }

 

                // 找到高於 num[i] 並且離 num[i] 最近的

 

                if ((num[j] - num[i]) > 0 && num[j] - num[i] < min_right)

                {

                    min_right = num[j] - num[i];

                }

            }

 

            sum += min_left + min_right;

        }

 

        cout << sum << '\n';

    }

 

    return 0;

}

 

void Sort(int n, int num[], int address[])

{

    int min;

 

    for (int i = 0; i < n; i++)

    {

        min = i;

 

        for (int j = i + 1; j < n; j++)

        {

            if (address[min] > address[j])

            {

                min = j;

            }

        }

 

        swap(address[min], address[i]);

        swap(num[min], num[i]);

    }

 

    return;

}

 
#29996: Re:請問為何到第五筆測資就TLE了


s111010137@student.nqu.edu.tw (Khazix)

學校 : 國立金門大學
編號 : 177202
來源 : [1.172.139.67]
最後登入時間 ：
2022-11-09 22:20:56
f607. 3. 切割費用 -- 2021年1月APCS | From: [39.10.161.177] | 發表日期 : 2022-04-19 23:04

 

using namespace std;

int num[200001] = { 0 };

int address[200001] = { 0 };

void Sort(int n, int num[], int address[]);

int main(void)

{

....

....

   


/ 111-04-18-Zerojudge-f607_3. 切割費用 #include <iostream> #include <iomanip> #include <algorithm> using namespace std; int num[200001] = { 0 }; int address[200001] = { 0 }; bool lock[10000001] = { 0 }; void Sort(int n, int num[], int address[]); int main(void) { cin.tie(0); std::ios::sync_with_stdio(false); int n, l; while (cin >> n >> l) { long long int sum = 0; for (int i = 0; i < n; i++) { cin >> num[i] >> address[i]; } Sort(n, num, address); for (int i = 0, t; i < n; i++) { t = num[i]; while (t >= 0) { if (lock[t] == 1 || t == 0) { sum += num[i] - t; break; } t--; } t = num[i]; while (t <= l) { if (lock[t] == 1 || t == l) { sum += t - num[i]; break; } t++; } lock[num[i]] = l; } cout << sum << endl; } return 0; } void Sort(int n, int num[], int address[]) { int min; for (int i = 0; i < n; i++) { min = i; for (int j = i + 1; j < n; j++) { if (address[min] > address[j]) { min = j; } }

swap(address[min], address[i]); swap(num[min], num[i]); } return;

}

 

然後這個反而比較快??

 
#29997: Re:請問為何到第五筆測資就TLE了


s111010137@student.nqu.edu.tw (Khazix)

學校 : 國立金門大學
編號 : 177202
來源 : [1.172.139.67]
最後登入時間 ：
2022-11-09 22:20:56
f607. 3. 切割費用 -- 2021年1月APCS | From: [39.10.161.177] | 發表日期 : 2022-04-19 23:06

 

 

   

 

 

然後這個反而比較快??

//這個

#include <iostream>

#include <iomanip>

#include <algorithm>

using namespace std;

int num[200001] = { 0 };

int address[200001] = { 0 };

bool lock[10000001] = { 0 };

void Sort(int n, int num[], int address[]);

int main(void)

{

    cin.tie(0);

    std::ios::sync_with_stdio(false);

 

    int n, l;

 

    while (cin >> n >> l)

    {

        long long int sum = 0;

 

        for (int i = 0; i < n; i++)

        {

            cin >> num[i] >> address[i];

        }

 

        Sort(n, num, address);

 

        for (int i = 0, t; i < n; i++)

        {

            t = num[i];

 

            while (t >= 0)

            {

                if (lock[t] == 1 || t == 0)

                {

                    sum += num[i] - t;

                    break;

                }

 

                t--;

            }

 

            t = num[i];

 

            while (t <= l)

            {

                if (lock[t] == 1 || t == l)

                {

                    sum += t - num[i];

                    break;

                }

 

                t++;

            }

 

            lock[num[i]] = l;

 

        }

 

        cout << sum << endl;

    }

 

    return 0;

}

 

void Sort(int n, int num[], int address[])

{

    int min;

 

    for (int i = 0; i < n; i++)

    {

        min = i;

 

        for (int j = i + 1; j < n; j++)

        {

            if (address[min] > address[j])

            {

                min = j;

            }

        }

 

        swap(address[min], address[i]);

        swap(num[min], num[i]);

    }

 

    return;

}

 

 

 
#29998: Re:請問為何到第五筆測資就TLE了


cges30901 (cges30901)

學校 : 不指定學校
編號 : 30877
來源 : [39.9.74.255]
最後登入時間 ：
2024-10-14 22:20:08
f607. 3. 切割費用 -- 2021年1月APCS | From: [110.26.168.226] | 發表日期 : 2022-04-20 10:02
1.

        for (int i = 0; i < n; i++)

        {

            int min_left = num[i] - 0;

            int min_right = l - num[i];

 

            for (int j = 0; j < i; j++)

            {

                // 找到低於 num[i] 並且離 num[i] 最近的

 

                if ((num[i] - num[j]) > 0 && num[i] - num[j] < min_left)

                {

                    min_left = num[i] - num[j];

                }

 

                // 找到高於 num[i] 並且離 num[i] 最近的

 

                if ((num[j] - num[i]) > 0 && num[j] - num[i] < min_right)

                {

                    min_right = num[j] - num[i];

                }

            }

 

            sum += min_left + min_right;

        }

 

        cout << sum << '\n';

    }


 2.

void Sort(int n, int num[], int address[])

{

    int min;

 

    for (int i = 0; i < n; i++)

    {

        min = i;

 

        for (int j = i + 1; j < n; j++)

        {

            if (address[min] > address[j])

            {

                min = j;

            }

        }

 

        swap(address[min], address[i]);

        swap(num[min], num[i]);

    }

 

    return;

}


1. 這樣子找前一個和後一個比較慢，可以用內建的set比較容易，參考這個解題報告：https://zerojudge.tw/ShowThread?postid=26545&reply=0

2. 排序太慢，用快一點的演算法吧，內建的sort也可以

 
ZeroJudge Forum