ACM 10038 Jolly Jumpers

Question

我寫了Jolly Jump problem（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; 
} 

但conmmited結果時間超過限制。爲什麼？我如何修改我的代碼以降低運行時間？

Answer 1

您的程序可能超出了時間限制，因爲它永遠不會結束。如果/當scanf()回報EOF，下面將永不停止循環：

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

在這些在線編程問題，它通常是一個好主意，至少運行你的建議對他們在這一問題提出，並查看示例數據解決方案如果你得到預期的產出。如果你的程序沒有產生預期的輸出，那麼你知道你有一個問題需要解決（並且你有一些具體的調試）。

Answer 2

我已經回答過了。

我所做的是將每兩個相應元素的差異添加到一個矢量，並在最後對它進行排序。

現在你需要做的只是檢查這個向量的每個元素是否比前一個元素多1。此外，檢查此排序向量的第一個元素爲1，最後一個爲n-1。

Answer 3

無限循環！只需將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