现在的位置: 首页 > 综合 > 正文

UVa Problem 846 Steps (数轴行走)

2012年07月18日 ⁄ 综合 ⁄ 共 868字 ⁄ 字号 评论关闭
// Steps (数轴行走)
// PC/UVa IDs: 110608/846, Popularity: A, Success rate: high Level: 2
// Verdict: Accepted
// Submission Date: 2011-09-25
// UVa Run Time: 0.016s
//
// 版权所有(C)2011,邱秋。metaphysis # yeah dot net
//
// 所走步数对应的序列如果左右对称,那么所走的步数应该是最少的。因为最先一步和最后一步长度均必须是
// 1,又由于每一步的长度必须是非负整数,且要么比上一步步长恰好大 1,要么相等,要么小 1,则左右对
// 称的序列能在最少步数得到最大距离。如果采取左右对称的走法,设两点距离为 distance,n = sqrt
// (distance),则由于最大步数为 n 步时能达到的距离是 1 + 2 + 3 + ... + (n - 1) + n +
// (n - 1) + ... + 3 + 2 + 1 = n^2。比较两点距离 distance 与 n^2,若相等,表明只需走
// 2 * (n - 1) + 1 = 2 * n - 1 步,否则若剩余距离 distance - n^2 在 1 - (n + 1),
// 只需插入一步即可,若 distance - n^2 大于 (n + 1),则需多插入两步即可。
	
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
	
using namespace std;
	
int main(int ac, char *av[])
{
	int cases, x, y;
	
	cin >> cases;
	while (cases--)
	{
		cin >> x >> y;
		int distance = y - x;
		
		if (distance <= 3)
			cout << distance << endl;
		else
		{
			int n = sqrt(distance);
		
			if (n * n == distance)
				cout << (2 * n - 1) << endl;
			else if ((distance - n * n) <= n)
				cout << (2 * n) << endl;
			else
				cout << (2 * n + 1) << endl;
		}
	}
	
	return 0;
}

抱歉!评论已关闭.