Long Legs

题面翻译

给你一个无限大小的棋盘，一个机器人初始位置为 $(0,0)$，初始每次可移动的长度为 $1$。
对于一个当前在 $(x,y)$ 的机器人，且它当前的可移动长度为 $m$（初始为 $1$)。则它可以耗费一个时间进行如下操作：
$\qquad$ 1. 移动到 $(x+m,y)$。
$\qquad$ 2. 移动到 $(x,y+m)$。
$\qquad$ 3.使得 $m=m+1$。
注意：在当前位置使得 $m=m+1$ 后会影响后面的操作。

现在给你两个正整数 $a,b(1 \leq a,b \leq 10^9)$，问机器人最少需要多少单位时间可以到达 $(a,b)$。

题目描述

A robot is placed in a cell $ (0, 0) $ of an infinite grid. This robot has adjustable length legs. Initially, its legs have length $ 1 $ .

Let the robot currently be in the cell $ (x, y) $ and have legs of length $ m $ . In one move, it can perform one of the following three actions:

jump into the cell $ (x + m, y) $ ;
jump into the cell $ (x, y + m) $ ;
increase the length of the legs by $ 1 $ , i. e. set it to $ m + 1 $ .

What's the smallest number of moves robot has to make to reach a cell $ (a, b) $ ?

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases.

The only line of each test case contains two integers $ a $ and $ b $ ( $ 1 \le a, b \le 10^9 $ ) — the ending cell.

输出格式

For each test case, print a single integer — the smallest number of moves the robot is required to make to reach a cell $ (a, b) $ from a cell $ (0, 0) $ .

样例 #1

样例输入 #1

样例输出 #1

2
5
6

提示

In the first testcase, the robot can first jump to $ (0, 1) $ , then to $ (1, 1) $ . If it ever increases the length of its legs, it will only be able to jump past $ (1, 1) $ .

In the second testcase, the robot can jump to $ (1, 0) $ , then increase the length of its length to $ 2 $ and jump three times to reach $ (1, 6) $ .

In the third testcase, the robot can increase the length of its legs three times to make it $ 4 $ . Then jump to $ (0, 4) $ . Then jump twice to reach $ (8, 4) $ .

分析

第三种操作进行次数太少时, m 太小, 需要的时间就会增加, 但如果 m 过大, 第三种操作浪费了太多的步数, 也会导致时间边长

我们的策略是: 先选好一个合适的 m , 然后以这个 m 来跳格子

终点是 (a, b) , 以x轴为例:

当 a 可以被我们选好的 m 整除时, 跳到 (a, 0) 的步数是 $\frac{a}{m}$ ,
当 a 不能被整除时, 我们以 m 去跳最多能跳到 $\left [ \frac{a}{m}\right ]$ 位置, 剩下的部分一定小于 m , 记为 k , 我们在增加步长的过程中肯定会出现 m = k 的时候, 我们只需要在这个时候以步长 k 跳一次格子即可, 跳到 (a, 0) 的步数就是 $\left [ \frac{a}{m}\right ] + 1$

对于y轴同理, 能整除就是 $\frac{b}{m}$ , 不能整除就是 $\left [ \frac{b}{m}\right ] + 1$

再加上增加步长需要的操作次数 (m - 1) , 总的操作次数就是: $x到a的步数 + y到b的步数 + (m - 1)$

我们只需要1开始枚举合适的步长 m , m 最大是不会超过 $3 \times 10^5$ 的

为什么 m 最大不超过 $3 \times 10^5$ 呢?

我们发现, a和b均不能被m整除时的总操作次数和 a和b均可以被m整除的总操作次数之间也就差2, 随便选一种来讨论

已知: $m + n \le 2 \sqrt{mn}$ , 当且仅当 $m = n$ 时取到等于号

那么对于总操作次数来说有 $\frac{a + b}{m} + m - 1\le 2\sqrt{\frac{a + b}{m}}-1$ , 要想操作次数取最小, 即是 $\frac{a+b}{m} = m$ , 即$m = \sqrt{a+b}$

当 a = b = $10^9$ 时, m不过也就是 $\sqrt{2} \times 10^\frac{9}{2}$ , 是不会超时的

代码

#include <iostream>
using namespace std;
const int N = 3e5;
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int t; cin >> t;
	while (t--)
	{
		int a, b; cin >> a >> b;
		
		int ans = N;
		for (int i = 1; i <= N; i++)
		{
			int t = (a / i) + (a % i != 0) + (b / i) + (b % i != 0) + i - 1;
			ans = min(ans, t);
		}
		cout << ans << endl;
	}
}

JZTXT

CF1814B