[問題] 記憶體使用過大

[kevin771012 (凱)]

題目：
        該天的最小波動值=min{|該天以前某一天的營業額-該天營業額|}

        當最小波動值越大時，就說明營業情況越不穩定。
        而分析整個公司的從成立到現在營業情況是否穩定，
        只需要把每一天的最小波動值加起來就可以了。
        你的任務就是編寫一個程序幫助 Tiger 來計算這一個值。
        第一天的最小波動值為第一天的營業額。

輸入說明：

第一行為正整數n(n<=32767) ，表示該公司從成立一直到現在的天數，
接下來的 n 行每行有一個正整數ai(|ai|<=1000000)， 表示第 i 天公司的營業額。

輸出說明：

輸出文件僅有一個正整數，即每一天的最小波動值之和。結果小於2147483648 。

作答如下：

//a066: HNOI2002營業額統計

import java.util.Scanner;
public class a066 {
        public static void main(String[] args) {
                Scanner sin = new Scanner(System.in);
                while(sin.hasNext()){
                        int a = sin.nextInt();
                        int ans = 0;
                        int[] b = new int[a];
                        for(int i=0;i<a;i++){
                                b[i] = sin.nextInt();
                                int min = 1000000;
                                if(i==0){
                                    min = b[i];
                                }
                                for(int j=0;j<i;j++){
                                    min = Math.min(min, Math.abs(b[i]-b[j]));
                                }
                                ans +=min;
                        }
                        System.out.println(ans);
                }
        }
}

送judge  NA 原因有兩個 一個是TLE ， 一個是MLE
不知道有沒有演算法可以解決類似的程式呢~?

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 163.24.253.85
※ 編輯: kevin771012     來自: 163.24.253.85        (03/08 22:49)
→ akasan:這題用遞迴解很強大的說
→ tkcn:唔，是遞迴呀，我以為是排序的說
→ tkcn:我看錯題目了，這樣遞迴指的是 binary search?
→ bleed1979:我是建樹，除了測資1和測資9以外，有一個測點還是TLE。
→ bleed1979:目前是使用陣列標記就可以了，但測資有負數很怪？