發表新討論
#4948: NA 因為記憶體使用過大


Kaitang (凱)

學校 : 國立屏東大學
編號 : 5159
來源 : [163.24.254.195]
最後登入時間 ：
2013-10-22 15:10:17
a066. HNOI2002 营业额统计 -- HNOI2002 | From: [163.24.253.85] | 發表日期 : 2011-03-08 22:33
//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);
}
}
}
 
本機測試都OK 但是記憶體使用過大所以NA 不知道有沒有更好的演算法可以解 

 
#4949: Re:NA 因為記憶體使用過大


liouzhou_101 (王启圣)

學校 : 广西柳州高级中学
編號 : 3714
來源 : [126.108.190.144]
最後登入時間 ：
2023-07-21 17:40:51
a066. HNOI2002 营业额统计 -- HNOI2002 | From: [116.253.11.112] | 發表日期 : 2011-03-08 23:04
//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
b[i] = sin.nextInt();
int min = 1000000;
if(i==0){
min = b[i];
}
for(int j=0;j
min = Math.min(min, Math.abs(b[i]-b[j]));
}
ans +=min;
}
System.out.println(ans);
}
}
}
本機測試都OK 但是記憶體使用過大所以NA 不知道有沒有更好的演算法可以解 


真不好意思，看来JAVA的记忆体用量的确比较大，于是将空间限制开到8MB。
顺便一提，您的做法不是期望中的做法，是会吃TLE的，您应该往更快的做法去想。
题目中N<=32767，时间复杂度是O(N^2)肯定是会TLE的啊...
 
#4955: Re:NA 因為記憶體使用過大


david942j (文旋)

學校 : 臺北市立成功高級中學
編號 : 6086
來源 : [115.43.75.16]
最後登入時間 ：
2017-02-18 13:17:39
a066. HNOI2002 营业额统计 -- HNOI2002 | From: [203.71.24.170] | 發表日期 : 2011-03-09 16:05
//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
b[i] = sin.nextInt();
int min = 1000000;
if(i==0){
min = b[i];
}
for(int j=0;j
min = Math.min(min, Math.abs(b[i]-b[j]));
}
ans +=min;
}
System.out.println(ans);
}
}
}
本機測試都OK 但是記憶體使用過大所以NA 不知道有沒有更好的演算法可以解 


真不好意思，看来JAVA的记忆体用量的确比较大，于是将空间限制开到8MB。
顺便一提，您的做法不是期望中的做法，是会吃TLE的，您应该往更快的做法去想。
题目中N<=32767，时间复杂度是O(N^2)肯定是会TLE的啊...

目前想到的AVLtree可解 
ZeroJudge Forum