AT4303 [ABC119D] Lazy Faith[题解][二分]

AT4303

translation

有 \(a\) 个点 \(s\)，有 \(b\) 个点 \(t\)，问从点 \(x\) 出发到达至少一个 \(a\) 和一个 \(b\) 的最短距离是多少。

solution

我们先举一个简单的例子，假如我们有 \(2\) 个点 \(s\) 分别在 \(3,6\) 和 \(2\) 个点 \(t\) 分别在 \(2,5\)，\(x\) 从 \(4\) 出发。

先画一个图更好的理解

那么我们现在有 \(4\) 种选择：

选择 \(s_1\) 和 \(t_1\)
选择 \(s_2\) 和 \(t_2\)
选择 \(s_1\) 和 \(t_2\)
选择 \(s_2\) 和 \(t_1\)

那么可以想想，还有其他的选择吗？并没有！

因为要选择最短的路线，如果在 \(t_1\) 左边或 \(s_2\) 右边还有点的话，若选择它肯定距离长，肯定要舍。

所以总结，只有这四种选法：

左 \(s\) 左 \(t\)
右 \(s\) 右 \(t\)
左 \(s\) 右 \(t\)
右 \(s\) 左 \(t\)

所以只要将这 \(4\) 种选法都算出来，取 \(\min\) 即可。

那如何算？

第一个问题：

如何找到在左/右边离 \(x\) 最近的 \(s/t\)？

这里我们就要用到二分

众所周知用二分可以用 lower_bound 和 upper_bound 函数。

我们在这里简单介绍一下这两种函数。

lower_bound

此函数通过二分的原理，在 \(a\) 数组中找到第一个 \(\leq x\) 的数。

使用：lower_bound(a + 1, a + n + 1, x)
upper_bound

使用方法与 lower_bound 类似，但是找到第一个 \(\le x\) 的数。

那么我们找到在左/右边离 \(x\) 最近的 \(s/t\) 就很容易了。

code

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <string>

#include <cstring>

#define int long long

using namespace std;

const int NR = 1e5 + 5;

int a, b, q;

int s[NR], t[NR];

void solve() {

	int x;

	cin >> x;

	int ss = lower_bound(s + 1, s + a + 1, x) - s;

	int sm = lower_bound(t + 1, t + b + 1, x) - t;

	int ans = 9e18;

	//左社左寺

	if (ss > 1 && sm > 1) {

		ans = min(ans, max(x - s[ss - 1], x - t[sm - 1]));

	}

	//右社右寺

	if (ss <= a && sm <= b) {

		ans = min(ans, max(s[ss] - x, t[sm] - x));

	}

	//左社右寺

	if (ss > 1 && sm <= b) {

		if (x - s[ss - 1] <= t[sm] - x) //如果左比右近或两边距离出发点相等，就先走左边

			ans = min(ans, (x - s[ss - 1]) * 2 + (t[sm] - x));

		else

			ans = min(ans, (t[sm] - x) * 2 + (x - s[ss - 1]));

	}

	//右社左寺

	if (ss <= a && sm > 1) {

		if (s[ss] - x <= x - t[sm - 1]) //如果右比左近，就先走右边

			ans = min(ans, (s[ss] - x) * 2 + (x - t[sm - 1]));

		else

			ans = min(ans, (x - t[sm - 1]) * 2 + (s[ss] - x));

	}

	cout << ans << endl;

	return;

}

signed main() {

	cin >> a >> b >> q;

	for (int i = 1; i <= a; i++) cin >> s[i];

	for (int i = 1; i <= b; i++) cin >> t[i];

	sort(s + 1, s + a + 1);

	sort(t + 1, t + b + 1);

	while (q--) solve();

	return 0;

}

巴特西

【题解】「AT4303」[ABC119D] Lazy Faith

AT4303 [ABC119D] Lazy Faith[题解][二分]

translation

solution

code

最新文章

热门文章