题解 | #传递#

#传递#

链接：https://ac.nowcoder.com/acm/contest/40639/D 来源：牛客网

题目描述

*两只小青蛙 A 和 B 想从河的一端跳到另一端，它们分别选择了一条道路，每条道路上都有 nn 个石子，A 在第一条道路上进行跳跃，B 在第二条道路上进行跳跃。双方不能跳到对方的道路上，青蛙只能跳到石子上，不能跳到河里。青蛙只能前进，不能后退，可以一次跳过多个石子，不必逐个石子向前跳。青蛙的跳跃距离至多为 mm，但是他们有一个助跳器，可以让自己的跳跃距离上限变为 k(m < k)k(m<k)。

初始时跳跃器在青蛙 A 手中，它们虽然不在一个道路上，但是可以相互传递跳跃器。即 A 可以将跳跃器传给 B，B 也可以将跳跃器传给 A。但是如果他们距离之差超过 q(k < q)q(k<q)，则无法传递。

请问两只青蛙都跳到终点(第 nn 个石子)最少需要传递几次助跳器？

保证相邻石子的距离之差小于 kk，可以证明两只青蛙一定可以都抵达终点。

大致思路：贪心地想:如果A一定要传给B,则A最多能到达(B现在能到达的最远距离+q)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1010;
int n, m, k, q, la, lb, ans;
bool flag = true;//flag为true时助跳器在A身上,flag为false时助跳器在B身上
int a[N], b[N];

int main() {
	cin >> n >> m >> k >> q;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++)
		cin >> b[i];
	for (;;) {
		if (flag) {//助跳器在A身上时
			while (b[lb + 1] - b[lb] <= m && lb + 1 <= n)
				lb++;
			//B能到达的最远距离
			if (lb == n) //如果B能调到终点,则A一定能
				break;
			while (a[la + 1] - b[lb] <= q && la + 1 <= n)
				la++;
			//贪心地想:如果A一定要传给B,则A最多能到达(B现在能到达的最远距离+q)
			if (la == n) {//如果A能跳到终点
				while (b[lb + 1] - b[lb] <= m && lb + 1 <= n)
					lb++;
				//B不用助跳器不能到达终点就需要再传一次
				if (lb < n)
					ans++;
				break;
			}
			//必须传一次
			ans++;
			flag = false;
		} else { //同理
			while (a[la + 1] - a[la] <= m && la + 1 <= n)
				la++;
			if (la == n) {
				break;
			}
			while (b[lb + 1] - a[la] <= q && lb + 1 <= n)
				lb++;
			if (lb == n) {
				while (a[la + 1] - a[la] <= m && la + 1 <= n)
					la++;
				if (la < n)
					ans++;
				break;
			}
			ans++;
			flag = true;
		}
	}
	cout << ans << endl;
}