竹園論壇

標題: TOJ - 147 [打印本頁]

作者: jd3 時間: 2014-10-4 23:36
標題: TOJ - 147
本帖最後由 jd3 於 2014-10-5 21:27 編輯

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

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

沒錯我只會O(N^3)...

作者: xiplus 時間: 2014-10-5 10:39
本帖最後由 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);

    }

}

作者: domen111 時間: 2014-10-5 12:25
首先你必須先排序(不然甚麼優化都不用做了)

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

歡迎光臨竹園論壇 (http://forum.tfcis.org/)