526互联

Educational Codeforces Round 145 (Rated for Div. 2) B. Points on Plane

发布时间 2023-10-21 19:24:24作者: zsxuan

给一个二维平面，你需要在上面放 \(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;
}