小L的散步

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

题目概述 小L在一条由 n 个石块铺成的道路上散步，第 i 个石块的长度为 xᵢ。每个石块的右端点（包括最后一个）被视为一个缝隙。他的脚掌长度为 l，初始时脚后跟位于位置 0。他总共走 m 步，每步跨过的长度为 y i。需要判断：在初始位置以及每步走完后，他的脚掌覆盖左闭右开区间 [p, p+l)]（p 为脚后跟当前位置）内是否包含了任何一个缝隙（边缘恰好位于 p 或 p+l 不算踩中）。 思路分析 我们需要确定所有缝隙的位置：通过计算石块长度的前缀和，我们可以轻松得到所有缝隙的位置（即每个石块的右端点），且这些位置是递增有序的。那么，如何高效判断一个区间内是否有缝隙呢？由于缝隙有序，我们可以使用二分查找来快速定位。对于给定的脚后跟位置 p，我们只需要找到第一个大于 p 的缝隙，然后检查这个缝隙是否小于 p + l。如果是，则说明这个缝隙落在了 (p, p+l) 区间内，即踩中了缝隙。 总结概括 这道题考察的是将实际问题模型化，并选择合适的数据结构进行优化。代码的核心在于前缀和预处理加二分查找。前缀和帮助我们快速得到缝隙位置，二分查找则完美应对了大数据量的挑战。整个代码结构清晰，逻辑严谨，是“模拟+二分”思想的一个典型应用。 C++代码展示如下：

#include<bits/stdc++.h>
using namespace std;
int find2(const vector<long long>& gaps, long long p) {
	int low = 0, high = gaps.size();
	while (low < high) {
		int mid = low + (high - low) / 2;
		if (gaps[mid] > p) {
			high = mid;
		} else {
			low = mid + 1;
		}
	}
	return low;
}
int main() {
	long long n,m,l;
	cin>>n>>m>>l;
	vector <long long> z(n);
	long long sum=0;
	for (long long i=0; i<n; i++) {
		long long x;
		cin>>x;
		sum+=x;
		z[i]=sum;
	}
	long long p=0;
	int d=find2(z,p) ;
	if(d<n&&z[d]<p+l) {
		cout<<"YES";
		return 0;
	}
	for(long long i=0; i<m; i++) {
		long long step;
		cin>>step;
		p+=step;
		d=find2(z,p);
		if(d<n&&z[d]<p+l) {
			cout<<"YES";
			return 0;
		}
	}
	cout<<"NO";
	return 0;
}