给一个二维平面，你需要在上面放 \(n\) 个芯片。将一个芯片放在 \((x, y)\) 的代价为 \(|x| + |y|\) 。放 \(n\) 个代价的代价为，所有芯片中耗费的最大代价。并且你需要保证任意两个芯片之间的距离严格 \(> 1\) 。
现在给出 \(n\) 给芯片，询问放 \(n\) 个芯片的最小代价。
一：不难想到 \(n\) 个芯片的最小代价为，所有芯片中的最大代价，于是保证任意两芯片距离 \(> 1\) 的情况下，使最大代价最小即可。
二：不难想到芯片和代价成正比例相关，于是可以二分。
三：假设代价为 \(k\) ，把握两个关键点：
- \(|x| + |y| \leq k\)
- \(|p_i - p_j| > 1\)
于是不妨按 \(x\) 坐标进行分组，由于大组会受到小组的影响，需要从边界开始考虑。
- \(x = k\) ，有 \(y = 0\) 对应的 \(1\) 个点满足。
- \(x = k - 1\) ，有 \(y = \{0, 1,-1\}\) 对应的 \(3\) 个点满足 \(|x| + |y|\) ，但需要和 \(x = k\) 的点间距 \(> 1\) 。于是只有 \(3 - 1 = 2\) 个点满足条件。
- \(x = k - 2\) ，有 \(y = \{0, -1, 1, -2, 2\}\) 对应的 \(5\) 个点满足 \(|x| + |y| \leq k\) ，但需要和 \(x = k\) 的点间距 \(> 1\) ，于是只有 \(5 - 2 = 3\) 个点满足条件。
- \(\cdots\)
- \(x = 0\) ，有 \(k\) 个点满足条件。
- \(\cdots\)
- 负数同理
则 \(k \sim 0\) 对应的点数为 \(1, 2, 3, \cdots, k + 1\) ，同理 \(-1 \sim -k\) 对应的点数为 \(k, k-1, \cdots, 1\) 。
则 \(k\) 的代价最多能支持 \(k + 1 + \frac{k(1+k)}{2} \times 2 = (k+1)^2\) 。于是 \(k\) 的代价可支持点的区间为 \([k^2 + 1, (k + 1)^2]\) 。
已知答案位置，求区间范围，是经典二位可解决的问题。 \(n \in [k^2 + 1，(k+1)^2]\) ，于是可以二分到最后一个 \(k\) 满足 \(k^2 + 1 \leq n\) 或者第一个 \(k\) 满足 \((k+1)^2 \geq n\) 。
view
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
void solve(){
ll n; std::cin >> n;
ll L = 0 - 1, R = 1E9 + 1;
while ( R - L > 1 ) {
ll M = ( R + L ) >> 1;
if ( M * M + 1 <= n) // 最后一个 k 满足 k^2 + 1 <= n
L = M;
else
R = M;
}
std::cout << L << "\n";
}
int main() {
int _ = 1; std::cin >> _;
while (_--) solve();
return 0;
}