自动搬运

查看原文

来自洛谷，原作者为

	L01001101 The world is splendid and grand, welcome home.

搬运于2025-08-24 22:57:05，当前版本为作者最后更新于2024-07-11 20:29:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Update on 2024.12.19，感谢 imljyhaha 的 Hack，已修改（。

P10341 [THUSC 2019] 紧急决策。

通过题目我们可以知道，只有 $[1,ans]$ 区间内的灯塔全被照亮才会对答案产生贡献。

考虑贪心，查找第一个未被照亮的灯塔 $i$，向右查找到最远且可以照亮灯塔 $i$ 的灯塔 $p$，点亮灯塔 $p$，并扩展灯塔 $p$ 可照亮的范围，重复上述操作直到点亮灯塔的次数用完。

此时最后一个被照亮的灯塔编号即为答案。

时间复杂度 $O(n)$。

#include<cstdio>
const int N=7.5e6+10;
int n,t,q;
int a[N];
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9')ch=='-'?f=0:0,ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return f?x:-x;
}
int main()
{
	n=read(),t=read(),q=read();
	for(int i=1;i<=n;++i)
		a[i]=read();
	int i=1,p=0;
	while(t--){
		++p;
		while(i<n&&a[i+1]-a[p]<=q)++i;
		p=i;
		if(i==n)return !printf("%d\n",n);
		while(p<n&&a[p+1]-a[i]<=q)++p;
	}
	printf("%d\n",p);
	return 0;
}