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 的大作中提到】
: 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 的大作中提到】
: 随着LLVM做得越来越好，这种把java byte code当intermediate representation的潮
: 流变得越来越没有必要了。
: scala的悲剧告诉我们：哪怕设计者再具匠心，扔给他 JVM 這個烂摊子，他也就很难有
: 所发挥了……
| z*******h
发帖数: 346 | 4 Scala code里的这些Queue啥的你用的是mutable 还是 immutable的？immutable的就是
慢啊。
【在 p*****2 的大作中提到】
: 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 的大作中提到】
: Scala code里的这些Queue啥的你用的是mutable 还是 immutable的？immutable的就是
: 慢啊。
| p*****2
发帖数: 21240 | 6
不过我感觉是OJ系统的问题。我在local run的话scala确实不慢。
【在 z*******h 的大作中提到】
: Scala code里的这些Queue啥的你用的是mutable 还是 immutable的？immutable的就是
: 慢啊。
| z*******h
发帖数: 346 | 7 那你java里用LinkedList implement Queue, 这就不公平嘛。你把scala里的
collection都换成mutable的，看看怎么样。我对scala速度还是很满意的。
【在 p*****2 的大作中提到】
:
: 不过我感觉是OJ系统的问题。我在local run的话scala确实不慢。
| p*****2
发帖数: 21240 | 8
本来用的就是mutable的。应该是系统的问题。local测试不慢
【在 z*******h 的大作中提到】
: 那你java里用LinkedList implement Queue, 这就不公平嘛。你把scala里的
: collection都换成mutable的，看看怎么样。我对scala速度还是很满意的。
| t***a
发帖数: 416 | 9 我们实际的项目用下来，和java比起来没有明显的性能差距
【在 p*****2 的大作中提到】
:
: 本来用的就是mutable的。应该是系统的问题。local测试不慢
| p*****2
发帖数: 21240 | 10
我感觉靠谱。你们用的2.10吗？OJ上用的2.09，不知道是不是2.09有些地方有性能问题
。
【在 t***a 的大作中提到】
: 我们实际的项目用下来，和java比起来没有明显的性能差距
|
|
