CF2037D Sharky Surfing 解题报告

是漂亮的玛拉妮耶！！！

题目大意

在数轴 1 \sim L 上跳跃，定义位于 x 时跳跃能力为 k 时可跳到区间 [x,x+k] 的任意位置，起初跳跃能力为 1。在数轴上有 n 个障碍物，每个障碍物（不重叠）占用的 [l_i,r_i] 不可到达；在数轴上还有 m 个增强道具，第 i 个增强道具位于 x_i 处（不会有障碍物但多个道具地方可能重叠），增强效果为跳跃能力提高 v_i。问至少捡多少增强道具能保证到达 L 处，若无法到达，输出 -1。

解题思路

考虑贪心：从前往后走的时候，如果遇到障碍物，则从当前遇到的所有道具里面选尽量大的肯定最优，因为这样能使得选的道具尽量少。

基于以上贪心，考虑用优先队列大根堆存下当前所遇到的所有增强道具，每遇到障碍物，从大往小选，直到当前的跳跃能力能够跳过当前障碍物（即如果障碍物的长度为 len_i，则此时的跳跃能力 v\ge len+1）。

3\le L\le 10^9

由于当前的数轴长度 L 过长，考虑只选取我们有用的数轴上的数字进行离散化，即道具的位置和障碍物的左端点。道具的效果和障碍物的长度可以通过结构体和离散化后的位置存在一起。从而就可以实现上述贪心。

离散化时间复杂度 O((n+m)\log(n+m))，贪心时间复杂度 O((n+m)\log m)，总时间复杂度 O((n+m)\log(n+m))。

AC Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#define N 400005//注意离散化数组范围 
using namespace std;
int T,n,m,L,cnt;
struct obs//obstacle 障碍物 
{
    int l,r,len;
}o[N];
struct tols//tools 增强道具 
{
    int x,v;
}t[N];
int bok[N],bl[N];//离散化数组 
priority_queue<int>q;//默认大根堆 
int re()//防止作弊不放快读快写
void wr(int x)
signed main()
{
    T=re();
    while(T--)
    {
        n=re(),m=re(),L=re();
        cnt=0;
        for(int i=1;i<=n;i++)
        {
            o[i].l=re(),o[i].r=re();
            o[i].len=o[i].r-o[i].l+1;
            bok[++cnt]=o[i].l;//离散化左端点 
        }
        for(int i=1;i<=m;i++)
        {
            t[i].x=re(),t[i].v=re();
            bok[++cnt]=t[i].x;//离散化道具位置 
        }
        sort(bok+1,bok+cnt+1);
        int boks=unique(bok+1,bok+cnt+1)-bok-1;
        for(int i=1;i<=n;i++)
            o[i].l=lower_bound(bok+1,bok+boks+1,o[i].l)-bok;
        for(int i=1;i<=m;i++)
            t[i].x=lower_bound(bok+1,bok+boks+1,t[i].x)-bok;//朴素的离散化 
        int nowo=0,nowt=0,ans=0,nowv=1,flag=0;
        //当前第几个障碍物，第几个道具，当前答案（捡的道具个数），当前跳跃能力，是否中途因跳跃能力不够而直接输出 -1 
        for(int i=1;i<=boks;i++)//遍历离散化后的位置 
        {
            while(i==t[nowt+1].x&&nowt<m)//下个位置有道具 
            {
                nowt++;
                q.push(t[nowt].v);//存入优先队列 
            }
            if(i==o[nowo+1].l&&nowo<n)//下个位置有障碍 
            {
                nowo++;
                int bas=o[nowo].len;
                while(q.size()!=0&&nowv<=bas)//拿道具 
                {
                    nowv+=q.top();
                    q.pop(),ans++;
                }
                if(!q.size()&&nowv<=bas)//道具拿满也不够跳过障碍 
                {
                    puts("-1");
                    flag=1;
                    break;
                }
            }
        }
        while(q.size())
            q.pop();//多测清空 
        if(!flag)
            wr(ans),putchar('\n');
    }
    return 0;
}