0

我已经编写了Jolly Jump 问题的解决方案代码（ACM 10038 uva）。我的代码如下：

#include<stdio.h>
#include<stdlib.h>

int main(){
  int count=0;
  int Number[3000]={0};
  int Absolute[3000]={0};
  bool flag=true;
  while(scanf("%d",&count)){
   for(int i=0;i<count;++i){
     scanf("%d",&Number[i]);
     Absolute[i]=0;
   }
   for(int j=0;j<count-1;++j){
     int diff=Number[j]-Number[j+1];
     if(diff<0)diff*=-1;
     Absolute[diff]=1;
   }
   flag=true;
   for(int x=1;x<count;++x){
     if(Absolute[x]!=1){
       flag=false;
       break;
     }
   }
   if(flag)printf("Jolly\n");
   else printf("Not Jolly\n");
 }
 return 0;
}

但提交的结果是超出时间限制。为什么？如何修改我的代码以降低运行时间？

4

3 回答 3

2

您的程序可能超过了时间限制，因为它永远不会完成。如果/何时scanf()返回EOF，以下内容将永远不会停止循环：

while(scanf("%d",&count)){
    // whatever...
}

在这些在线编程问题中，至少针对问题中提供的示例数据运行您提出的解决方案并查看是否获得预期输出通常是一个好主意。如果你的程序没有产生预期的输出，那么你就知道你有问题要解决（并且你有一些具体的东西要调试）。

于 2012-11-24T08:22:15.733 回答
1

无限循环！只需替换while(scanf("%d",&count))为while(scanf("%d",&count) != EOF)就完成了。

来自man scanf：

返回值

   These  functions  return  the  number  of  input items successfully
   matched and assigned, which can be fewer than provided for, or even
   zero in the event of an early matching failure.

   The  value  EOF  is  returned if the end of input is reached before
   either the  first  successful  conversion  or  a  matching  failure
   occurs.  EOF is also returned if a read error occurs, in which case
   the error indicator for the stream  (see  ferror(3))  is  set,  and
   errno is set indicate the error.

我也是竞争对手。我可以给您的一个提示是始终创建一个输入文件（in.txt）和一个输出文件（out.txt），将输入重定向到程序并使用以下方法比较输出diff：

$ cat in.txt
4 1 4 2 3
5 1 4 2 -1 6

$ cat out.txt
Jolly
Not jolly

$ ./jolly_jumpers < in.txt > my_out.txt

$ diff -s out.txt my_out.txt
Files out.txt and my_out.txt are identical
于 2012-11-26T22:24:22.280 回答
0

我之前已经回答过了。

我所做的是将每两个相应元素的差异添加到向量中，最后对其进行排序。

现在你需要做的只是检查这个向量的每个元素是否比前一个元素正好多 1。此外，检查此排序向量的第一个元素为 1，最后一个元素为 n-1。

于 2012-11-24T08:08:26.960 回答