题解 | #小L的三角尺#

题意：

现在小L面前有 n 个石块，第 i 个石块的长度为 𝑥 𝑖 x i ​ ，每两个相邻石块之间都有一个长度不计的缝隙。 小L一共走了 𝑚 m 步，每步跨过的长度为 𝑦 𝑖 y i ​ 。 小L的初始位置为 0，最左边的石块的位置也为 0，脚掌的长度为 𝑙 l，脚后跟位于 0 的位置，请问小L在散步的过程中是否有踩中石块的缝隙（最后一个石块的右端点也视为缝隙）。检查范围包含初始位置以及每一步走完后的位置，脚掌边缘位于缝隙不视为踩中。

核心思路：

这段代码采用前缀和 + 双指针的高效策略解决该问题，核心思路为：首先通过前缀和预处理得到两个递增数组，数组 a 存储所有石块缝隙的位置（a [i] 是前 i 个石块总长度，即第 i 个石块右侧缝隙），数组 b 存储小 L 所有待检查的脚后跟位置（b [0] 为初始位置，b [i] 是走完前 i 步后的位置）；随后用双指针 i（遍历 b 数组，覆盖初始和每步后所有位置）、j（遍历 a 数组的缝隙位置）进行单向遍历检查，对每个 b [i]，先移动 j 找到第一个大于 b [i] 的缝隙 a [j]，利用 a、b 数组的递增性，j 仅需单向移动无需回退，保证 O (n+m) 的时间复杂度；接着判定该缝隙 a [j] 是否严格落在当前脚掌覆盖区间 (b [i], b [i]+l) 内，若满足则说明踩中缝隙，直接输出 YES 并终止程序，若遍历完所有 i（至 i=m）都未满足该条件，则输出 NO，同时通过 ios 优化和数组定长实现输入输出与存储的效率提升，适配较大数据量的场景。

#include<bits/stdc++.h>
using namespace std;
inline void optimizeIO() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
}

int main() {
	optimizeIO();
	int n, m, x;
	long long l;
	cin >> n >> m >> l;
	long a[200007] = {0}, b[200007] = {0};
	for (int i = 1; i <= n; i++) {
		cin >> x;
		a[i] += a[i - 1] + x;
	}
	for (int i = 1; i <= m; i++) {
		cin >> x;
		b[i] += b[i - 1] + x;
	}
	for (int i = 0, j = 0; i <= m; i++) {
		while (a[j] <= b[i] && j <= n)
			j++;
		if (a[j] < b[i] + l && a[j] > b[i]) {
			cout << "YES";
			break;
		} else if (i == m)
			cout << "NO";
	}
	return 0;
}