专栏文章

题解:P10341 [THUSC 2019] 紧急决策

P10341题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miq6fehb
此快照首次捕获于
2025/12/03 23:43
3 个月前
此快照最后确认于
2025/12/03 23:43
3 个月前
查看原文

Solution

读完题很明显可以发现本题和最值有关,所以本题考虑使用 贪心 思想来解决,对于第 ii 个灯塔,找到最远的可将它点亮的灯塔将其点亮再存入答案即可,时间复杂度为 O(n)O(n)
(tip:请注意此题 数据范围

Code

CPP
#include<bits/stdc++.h>
#define forr(i,a,b) for(long long i=a;i<=b;i++)
using namespace std;
long long n,t,q,a[10000001],ans;//注意数据范围!!!(本人惨痛经历) 
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0); //输入输出加速
	cin>>n>>t>>q;
    a[n+1]=1e9;//一定要记得在 n+1 的地方设置 inf!!!(本人惨痛经历)
	forr(i,1,n) cin>>a[i];
	forr(i,1,n)//找最远的有效灯塔 
	{
		if(!t) break;
		forr(j,i,n)
		{
			if(a[j+1]-a[i]>q)
			{
				forr(x,j,n) //能够产生贡献的区域 
				{
					if(a[x+1]-a[j]>q)
					{
						ans+=x-i+1;
						i=x; //查找第 k 个灯塔 
						break;
					}
				}
				t--;
				break;
			}
		}
	}
	cout<<ans<<endl;
    return 0;//下次再见 
}
事已至此,不如留下赞和关注,后会有期。

评论

2 条评论,欢迎与作者交流。

正在加载评论...