TOJ - 147

jd3

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

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

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

xiplus

再給你看看我超短的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

首先你必須先排序(不然甚麼優化都不用做了)

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