p*****2 发帖数: 21240 | 1 java 400多毫秒,scala 1000毫秒超时。
object test6 extends App {
def add(x:Int, y:Int):Unit={
if(x<1 || x>n || y<0) return;
val yy=Math.min(y,a(x)+1)
if(v(x)(yy)) return
queue+=Array(x,yy)
v(x)(yy)=true
}
val sc=new Scanner(new File("input.txt"))
val out=new PrintWriter("output.txt")
val n=sc.nextInt
val a=new Array[Int](n+1)
val v=Array.ofDim[Boolean](105, 100005)
val queue=Queue[Array[Int]]()
for(i<-1 to n) a(i)=sc.nextInt
val r1=sc.nextInt
val c1=sc.nextInt
val r2=sc.nextInt
val c2=sc.nextInt
var distance=0
var count=1
add(r1,c1)
while(true){
for(i<-1 to count){
val Array(x,y)=queue.dequeue
if(x==r2 && y==c2){
out.println(distance)
out.close
exit(0)
}
add(x-1,y)
add(x+1,y)
add(x,y-1)
add(x,y+1)
}
distance+=1
count=queue.size
}
}
public class test {
int n;
int[] a;
int r1, c1, r2, c2;
boolean[][] v=new boolean[105][100005];
Queue queue=new LinkedList();
int distance=0;
int count=1;
void add(int x, int y){
if(x<1 || x>n || y<0) return;
y=Math.min(y,a[x]+1);
if(v[x][y]) return;
queue.offer(new int[]{x,y});
v[x][y]=true;
}
int run() throws Exception
{
Scanner sc=new Scanner(new File("input.txt"));
n = sc.nextInt();
a = new int[n+1];
for(int i=1; i<=n; i++){
a[i] = sc.nextInt();
}
r1 = sc.nextInt();
c1 = sc.nextInt();
r2 = sc.nextInt();
c2 = sc.nextInt();
add(r1,c1);
while(true){
for(int i=0;i
int[] curr=queue.poll();
int x=curr[0];
int y=curr[1];
if(x==r2 && y==c2) return distance;
add(x-1, y);
add(x+1, y);
add(x,y-1);
add(x,y+1);
; }
distance++;
count=queue.size();
}
}
public static void main(String[] args) throws Exception
{
PrintWriter out=new PrintWriter("output.txt");
out.println(new test().run());
out.close();
}
} | A*******t 发帖数: 443 | 2 随着LLVM做得越来越好,这种把java byte code当intermediate representation的潮
流变得越来越没有必要了。
scala的悲剧告诉我们:哪怕设计者再具匠心,扔给他 JVM 這個烂摊子,他也就很难有
所发挥了……
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : java 400多毫秒,scala 1000毫秒超时。 : object test6 extends App { : def add(x:Int, y:Int):Unit={ : if(x<1 || x>n || y<0) return; : val yy=Math.min(y,a(x)+1) : if(v(x)(yy)) return : queue+=Array(x,yy) : v(x)(yy)=true : } :
| d***q 发帖数: 1119 | 3
in terms of performance, JVM is not bad.
【在 A*******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 随着LLVM做得越来越好,这种把java byte code当intermediate representation的潮 : 流变得越来越没有必要了。 : scala的悲剧告诉我们:哪怕设计者再具匠心,扔给他 JVM 這個烂摊子,他也就很难有 : 所发挥了……
| z*******h 发帖数: 346 | 4 Scala code里的这些Queue啥的你用的是mutable 还是 immutable的?immutable的就是
慢啊。
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : java 400多毫秒,scala 1000毫秒超时。 : object test6 extends App { : def add(x:Int, y:Int):Unit={ : if(x<1 || x>n || y<0) return; : val yy=Math.min(y,a(x)+1) : if(v(x)(yy)) return : queue+=Array(x,yy) : v(x)(yy)=true : } :
| p*****2 发帖数: 21240 | 5
都是用immutable的。
【在 z*******h 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Scala code里的这些Queue啥的你用的是mutable 还是 immutable的?immutable的就是 : 慢啊。
| p*****2 发帖数: 21240 | 6
不过我感觉是OJ系统的问题。我在local run的话scala确实不慢。
【在 z*******h 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Scala code里的这些Queue啥的你用的是mutable 还是 immutable的?immutable的就是 : 慢啊。
| z*******h 发帖数: 346 | 7 那你java里用LinkedList implement Queue, 这就不公平嘛。你把scala里的
collection都换成mutable的,看看怎么样。我对scala速度还是很满意的。
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 不过我感觉是OJ系统的问题。我在local run的话scala确实不慢。
| p*****2 发帖数: 21240 | 8
本来用的就是mutable的。应该是系统的问题。local测试不慢
【在 z*******h 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 那你java里用LinkedList implement Queue, 这就不公平嘛。你把scala里的 : collection都换成mutable的,看看怎么样。我对scala速度还是很满意的。
| t***a 发帖数: 416 | 9 我们实际的项目用下来,和java比起来没有明显的性能差距
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 本来用的就是mutable的。应该是系统的问题。local测试不慢
| p*****2 发帖数: 21240 | 10
我感觉靠谱。你们用的2.10吗?OJ上用的2.09,不知道是不是2.09有些地方有性能问题
。
【在 t***a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我们实际的项目用下来,和java比起来没有明显的性能差距
|
|