查看: 639|回復: 6

[解決] TOJ - 147

[複製鏈接]
  • TA的每日心情
    鬱悶
    2015-5-15 22:38
  • 簽到天數: 33 天

    [LV.5]常住居民I

    75

    主題

    302

    帖子

    766

    積分

    版主

    TFcis - 105 附設監工官

    Rank: 7Rank: 7Rank: 7

    積分
    766

    台南一中資訊社程式設計達人 - 2014

    發表於 2014-10-4 23:36:14 | 顯示全部樓層 |閱讀模式

    趕快加入我們來參與討論吧!

    您需要 登錄 才可以下載或查看,沒有帳號?加入我們

    x
    本帖最後由 jd3 於 2014-10-5 21:27 編輯

    http://toj.twbbs.org/oj/pro/147/

    求O(N^2)和O(N * logN)做法

    沒錯我只會O(N^3)...
    <這是個人簽名欄位>
    回復

    使用道具 檢舉

  • TA的每日心情
    開心
    2017-8-20 13:10
  • 簽到天數: 319 天

    [LV.8]以壇為家I

    194

    主題

    363

    帖子

    1589

    積分

    金牌會員

    Rank: 6Rank: 6

    積分
    1589

    台南一中資訊社新手達陣

    發表於 2014-10-5 10:39:25 | 顯示全部樓層
    本帖最後由 xiplus 於 2014-10-5 10:40 編輯

    再給你看看我超短的code  不懂再問我吧XD不過我不知道我的作法時間複雜度多少(哈哈不會TLE就好啦
    [C++] 純文本查看 復制代碼
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    int main(){
        int n;
        while(~scanf("%d",&n)){
            int v[n];
            for(int q=0;q<n;q++)scanf("%d",&v[q]);
            sort(v,v+n);
            int min=2147483647;
            for(int q=0;q<=n-3;q++){
                for(int w=q+1;w<=n-2;w++){
                    if(v[q]+v[w]>v[w+1]){
                        if(min>v[q]+v[w]+v[w+1])min=v[q]+v[w]+v[w+1];
                        break;
                    }
                }
            }
            printf("%d\n",min);
        }
    }

    點評

    都已經看到兩層for迴圈了很明顯就是O(n^2)  發表於 2014-10-5 18:36
    回復 支持 反對

    使用道具 檢舉

  • TA的每日心情
    開心
    2015-4-12 10:09
  • 簽到天數: 137 天

    [LV.7]常住居民III

    142

    主題

    686

    帖子

    3559

    積分

    邁向天堂

    蘇多門

    Rank: 8Rank: 8

    積分
    3559

    新手達陣台南一中資訊社程式設計達人 - 2014

    發表於 2014-10-5 12:25:37 | 顯示全部樓層
    首先你必須先排序(不然甚麼優化都不用做了)

    第一個提示:
    在排序好的陣列中,取出三根可形成三角形的木棒a,b,c,其中a<=b<=c,可以證明出b和c一定是在陣列中連續的元素,如果不是連續的元素,那麼為何不要把c換成d,其中b<d<c,這樣的答案一定比原來更好,如果聽得懂這段大概就想得出n^2的算法了。

    點評

    jd3
    喔喔結果我想到了XD  發表於 2014-10-5 21:27
    jd3
    謝拉~這樣我就看懂了owo (然後再問一下神奇的O(N*logN))  發表於 2014-10-5 18:31
    jd3
    嗯嗯 感覺和之前有一題拿3根筷子的好像  發表於 2014-10-5 18:30
    蘇多門 domen111
    My Web: https://sites.google.com/site/domenprg/
    回復 支持 反對

    使用道具 檢舉

    您需要登錄後才可以回帖 登入 | 加入我們

    本版積分規則

    快速回覆 返回頂部 返回列表