主題

ZeroJudge - e556: 00846 - Steps　解題心得

Not In My Back Yard | 2019-12-07 22:50:27 | 巴幣 0 | 人氣 308

題目連結：

e556: 00846 - Steps

題目大意：

給定一正整數 n ，代表有 n 組測試資料，每筆佔一列。每列給定兩正整數 x 、 y （0 ≦ x ≦ y ＜ 2 ^ 31）。代表要從一維數線座標 x 走到 y 。

第一步以及最後一步的走的距離為 1 單位。接著的每一步可以比上一步多或是少一單位，也可以維持不變。求從 x 走到 y 最少所需的步數為何？

範例輸入：

3

45 48

45 49

45 50

範例輸出：

3

4

解題思維：

從起點 x 跟終點 y 兩端開始往中間走。一開始一次走一單位（有兩邊，所以一個「完整」步驟走兩單位）、接著增加距離變成一步走兩單位、三單位……以此類推。每做一個步驟步數就＋ 2 （因為是兩邊一起走）

當步伐 S 單位時，如果現在的左邊位置 x' ＋ 2S ＞現在的右邊位置 y' 時，則停止以上的步驟。

接著判斷 x' 與 y' 的關係。如果 x' ＝ y' 代表以上的方法剛剛好，所以現在的步數計量即是最少的；如果 x' ＋ S ＜ y' ，代表走兩步 S 會超過但單走一步 S 也不行，代表要跨兩步。所以是當前步數計量＋ 2 ；剩下的情況，代表只要走一步（不一定是走 S 單位）就可以了，因此步數＋ 1 。

當然，以上可步驟以化作公式解。但是因為直接模擬逼近的速度很快，所以也沒有那個必要。

本人的程式碼（於 CodePile 上）

此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。

#程式題目解題心得