尋找組織單向火車站交通算法的錯誤

Question

我寫下面的代碼來解決this railway station traffic programming contest question。 （您可以閱讀意見和建議的解決方案here）。但是，有一些例外的情況下，這些代碼不起作用。他們是什麼？

#include <stdio.h> 
#include <stdlib.h> 
int main(){ 
    int n, i,j; 
    int * array; 
    scanf("%i",&n); 
    array = malloc(sizeof(int) * n); 
    for(i=0;i<n;++i) scanf("%i",&array[i]); 
    for(i=0;i<n;++i){ 
     if(i+1 == array[i]) array[i] = -1; 
     else{ 
      if(array[i] < i+1){ 
       for(j=0;j<i;++j){ 
        if(array[i] == j+1){ 
         if(array[j] == -1){ 
          printf("No\n"); 
          return 0; 
         } 
         else array[i] = array[j] = -1; 
        } 
       } 
      } 
     } 
    } 
    for(i=0;i<n;++i) if(array[i] != -1) break; 
    if(i == n) printf("Yes\n"); 
    else printf("No\n"); 
    return 0; 
} 

P.S。：我假設這方案需要每時間（而不是等待一個0用於信令輸入的結尾）在一個條目。

這段代碼是應該做的：

1）我假設你已經讀過what's in this link。

2）將一個序列複製到一個數組後，我們必須驗證這個序列是否有效。

所以我們採用如下算法：

1. 遍歷序列，從第一個元素開始。

2. 如果element = element的索引+1（因爲C列表是零索引的），那麼element = -1。

3. 否則，當且僅當元素<元素的索引：我們查找一個前一個元素（當前元素==前一個元素索引+ 1）是有效的。如果找到這個元素，那麼現在元素和前一個元素都變爲-1。如果之前的元素之前已經被更改（即它已經是-1），那麼這不是一個有效的序列。

4. 如果像這樣迭代列表之後，仍有任何元素留下，這不是有效的序列。

實例：

實施例1

陣列：5 4 3 2 1

5:5> 0 + 1，則跳過。 4：4> 1 + 1，跳過。 3：3 == 2 + 1.然後3 - > -1。

陣列：5 4 -1 2 1

2：2 < 3 + 1 4具有1的索引和1 + 1 = 2。

陣列：5 -1 -1 -1 1

1:1 < 4 + 1 5具有的索引爲0和0 + 1 = 1。

陣列：-1 -1 -1 -1 -1

因此，這種序列是有效。

實施例2

陣列：5 4 1 2 3

5:5> 0 + 1，則跳過。 4：4> 1 + 1，跳過。 1：1 < 2 + 1。5具有索引0

陣列：-1 -1 4 2 3

2：2 < 3 + 1 4具有1

索引

陣列：-1 -1 -1 -1 3

3：3 < 4 + 1 -1（在位置2）具有2 2 + 1 = 3。 索引因此的序列是不有效。

Answer 1

這裏輸入您的代碼會給出錯誤的輸出的一個例子：

5 
3 4 2 5 1 

你介紹給英文代碼的轉譯，但並沒有深入瞭解爲什麼這樣的算法將解決這個問題。所以，我只去了其中一個額外的陣列用於跟蹤那些在車站車廂，這將有像堆棧（先入後出）起作用的解決方案：

#include <stdio.h> 
#include <stdlib.h> 
int main(){ 
    int n, i; 
    int carriageAtA = 1; 
    int * array; 
    int * station; 
    int stationSize = 0; 
    // Read input 
    scanf("%i",&n); 
    array = malloc(sizeof(int) * n); 
    station = malloc(sizeof(int) * n); 
    for(i=0;i<n;++i) scanf("%i",&array[i]); 
    // Iterate the desired carriages in sequence 
    for(i=0;i<n;++i) { 
     // While the last one in the station is not what we need: 
     while ((!stationSize || station[stationSize-1] != array[i]) && carriageAtA <= n) { 
      printf("Move %i from A to station\n", carriageAtA); 
      // Last carriage in station B is not what we need, so pull one in from A: 
      station[stationSize] = carriageAtA; 
      stationSize++; // There is now one more carriage in the station 
      carriageAtA++; // This is the next carriage at A 
     } 
     if (!stationSize || station[stationSize-1] != array[i]) { 
      // Could not find desired carriage at A nor at station. Give up. 
      printf("No\n"); 
      return 0; 
     } 
     // Drive last carriage at station to B: 
     printf("Move %i from station to B\n", array[i]); 
     stationSize--; 
    } 
    printf("Yes\n"); 
    return 0; 
} 

額外的printf調用只是爲了瞭解過程。滿意時將其移除。