526互联

* Codeforces Round 665 (Div. 2) A. Distance and Axis

发布时间 2023-10-15 22:26:41作者: zsxuan

有一个点 \(A\) 在 \(OX\) 正坐标轴上的 \(x\) 坐标为 \(n\) 。需要找到一个点 \(B\) ，使得 \(||OB| - |AB||= k\) 。

现在给出非负整数 \(n\) \(k\) ，你可以执行任意次以下操作：

  • 每步操作可以使 \(A\) 的坐标加一或减一。

询问最少需要进过多少次操作使 \(B\) 可以存在。

先假设出 \(x_B\) 的位置，令 \(x_B = m\) 。
由于只存在 \(XO\) 的正坐标轴，不难讨论出以下可能的分布情况：

  • 若 \(n \leq m\) ，即 \(O\ A\ B\) ： \(L = ||OB| - |AB|| = m - (m - n) = n\) 恒成立
  • 若 \(m \leq n\) ， \(O\ B\ A\) ： \(L = ||OB| - |AB|| = |(m - 0) - (n - m)| = |2m - n|\) 。

然后讨论 \(n\) 和 \(k\) 的关系。

  • 当 \(n < k\)， \(L < k\) 。不存在 \(B\) 。
  • 当 \(n = k\) ，显然存在 \(L = n = k\) 。于是 \(n < k\) 时将 \(n\) 移动到 \(k\) 为最小操作数。
  • 当 \(n > k\) 。
    • 若 \(n \leq m\) 显然 \(L = n > k\) ；
    • 若 \(m \leq n\) 左侧，则 \(L = |2m - n|\) 。设 \(L = k = |2m - n|\) ，则 \(m = \frac{\pm k + n}{2}\) 。由于 \(m\) 是个整数，若 \(k, n\) 的奇偶性相同则 \(A\) 不需要移动，否则需要移动一次。
view 
#include <bits/stdc++.h>
typedef long long ll;
void solve(){
	int n, k; std::cin >> n >> k;
	if (n < k) std::cout << k - n << '\n';
	else {
		if (~(n + k) & 1) std::cout << 0 << '\n';
		else std::cout << 1 << '\n';
	}
}
int main() {
	int _ = 1; std::cin >> _;
	while (_--) {solve();}
	return 0;
}