UVa846 - Steps (數論 Math theorm)

題目大意：

給你兩個數字，每次走的步伐必須為上一步的 +1 , -1 , 0 步伐，試問最短的步伐為?

分析:

數學題。

設第一個數字為 x ，第二個數字為 y
最好的情況為 x+1 , x+2 , …. , r , y-3 , y-2 , y-1
數列看起來相似於 梯形公式

以此得出策略為 → 每次將 n * 2 ( n 為上一步的 +1)

圖示如下:

• 1 2 3 2 1 轉變為 2 3 2

以此類推，透過這種方式每一次的 Step += 2

額外注意:

• 4 5 4
  將 4 刪除掉後，剩下 5 ，程式在下一次操作時，則會刪除掉兩個 5 ，但實際題目並沒有兩個 5 ，需要加上額外判斷

  如果 只有一個 5 時 則 step += 1

• 4 4
  將 4 刪除掉後，並沒有剩下任何東西，則下次會刪除兩個 5 ，但實際題目並沒有 5 ，所以不增加 Step 直接輸出

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
using namespace std;


int main()
{

    int intCase , x , y , intStep , intDistance , intSum , intLength ;
    cin >> intCase ;
    while(intCase--){
        cin >> x >> y ; 
        intStep = 0 ;
        intDistance = y - x ;
        intSum = 0 ;
        intLength = 0 ;
        //debug
        //cout << intDistance << '\n' << '\n' ;
        /*
        if(intDistance == 1){
            cout << 1 << '\n' ;
            continue ;
        }
        */
       
        while(++intLength){
            if(intSum + intLength * 2 > intDistance)
                break ;
            intSum += intLength * 2 ;
            intStep +=2;
        }
        //debug
        //cout << "intLength: " << intLength << '\n' ;
        //cout << "intSum: " << intSum << '\n' ;

        if(intSum + intLength < intDistance)
            intStep += 2 ;
        else if (intSum != intDistance )
            intStep ++ ;
        cout << intStep << '\n' ;


    }
    return 0;
}