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，那麼就剛好。

	#include <cstdio>
	using namespace std;
	int main()
	{
	// freopen ("input.txt","rt",stdin);
	int N;
	int x,y;
	scanf("%d",&N);
	while (N--){
	scanf("%d%d",&x,&y);
	int steps = 0, length;
	long long int sum = 0, distance = y-x;
	for (length=0;;) {
	length++;
	if (sum + 2*length > distance) break;
	sum += 2*length;
	steps += 2;
	}
	if (sum + length < distance) steps += 2;
	else if (sum != distance) steps += 1;
	printf("%d\n",steps);
	}
	return 0;
	}

view raw [UV] 846 Steps.cpp hosted with ❤ by GitHub