作者kevin771012 (凯)
看板java
标题[问题] 记忆体使用过大
时间Tue Mar 8 22:48:12 2011
题目：
该天的最小波动值=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)
1F：→ akasan:这题用递回解很强大的说 03/09 01:28
2F：→ tkcn:唔，是递回呀，我以为是排序的说 03/09 01:43
3F：→ tkcn:我看错题目了，这样递回指的是 binary search? 03/09 02:00
4F：→ bleed1979:我是建树，除了测资1和测资9以外，有一个测点还是TLE。 03/09 05:53
5F：→ bleed1979:目前是使用阵列标记就可以了，但测资有负数很怪？ 03/09 07:18