看著很簡單，結果一直killed....和同學討論半天才想出來

思路開始

n<=1000000，時間限制1s，用猜的要不是是 O(n) 就是 O(nlog n)

所以用來回反覆刷的方法必然行不通，最糟可能達到 O(n^2)

那就換個方向想，來回反覆刷的意思是經由順序，找出數字的由小到大

那把它改成經由數字大小，找出順序的順反(變向表示已經反彈)

for example :

  k     0  1  2  3  4  5

a[k]  4  1  5  2  3  6

數字找到的順序對應會是

  k     1  3  4  0  2  5

a[k]  1  2  3  4  5  6

可藉由順序的翻轉次數判定反彈幾次

沒錯！是不是想起了快速排序法，我會告訴你，不會過的喔！他最糟的狀況也有可能是O(n^2)

所以就要從輸入下手了....//接下來就考你自己了

看著很簡單，結果一直killed....和同學討論半天才想出來

 

思路開始

n<=1000000，時間限制1s，用猜的要不是是 O(n) 就是 O(nlog n)

 

所以用來回反覆刷的方法必然行不通，最糟可能達到 O(n^2)

那就換個方向想，來回反覆刷的意思是經由順序，找出數字的由小到大

那把它改成經由數字大小，找出順序的順反(變向表示已經反彈)

 

for example :

  k     0  1  2  3  4  5

a[k]  4  1  5  2  3  6

 

數字找到的順序對應會是

  k     1  3  4  0  2  5

a[k]  1  2  3  4  5  6

 

可藉由順序的翻轉次數判定反彈幾次

 

沒錯！是不是想起了快速排序法，我會告訴你，不會過的喔！他最糟的狀況也有可能是O(n^2)

所以就要從輸入下手了....//接下來就考你自己了

假設原陣列 before

後來的陣列 after

輸入完測資後

再將before的 index (0,1,2,3,4....)和value (1,4,2,5,3.....) ''反過來'' 儲存到 after 就不用進行排序了

也就是 after[before[i]-1] = i (i為for迴圈區域變數)

時間複雜度 : O(n)

我的方式 :　AC (0.1s, 8MB)　

後面就靠各位自己囉~