Solution - P10341

L01001101 · 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;
}