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

· · 题解

题目传送门 ＆ AC 记录

Solution

读完题很明显可以发现本题和最值有关，所以本题考虑使用 贪心 思想来解决，对于第 i 个灯塔，找到最远的可将它点亮的灯塔将其点亮再存入答案即可，时间复杂度为 O(n) 。

（tip：请注意此题 数据范围 ）

Code

#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;//下次再见 
}

事已至此，不如留下赞和关注，后会有期。