網頁

2014年1月21日 星期二

UVa 846 Steps

題意:
  給定兩地的位置x,y,其距離為(x-y),而第一步和最後一步的距離皆規定為1,每次踏下一步的距離只能比上一步的距離多1或少1或一樣,本題求最少走的步數,從Example來看x=45,y=50,距離為5,其最少步數為{1,2,2,1}。

想法:
  因為本題只要求最少的步數即可,因此過程如何安排就不重要,只要符合規定即可,所以我們可以先一步從起點一步從終點開始往中間走,變成{1,1},{1,2,2,1},{1,2,3,3,2,1}...這樣,舉個例子如果兩地距離為14,那麼剛才的算法到{1,2,3,3,2,1}就會停止,因為已經12了,在+2*4就會超過14,這時候只要判斷12+4<14,再走一步就可以了,我們不管這步應該排在哪個位置,反正這步的距離一定<=4。還要考慮另外兩種情況,分別是兩地距離如果為17,那麼12+4<17,就要再兩步,而如果兩地距離為12,那麼就剛好。