Codeforces之旅(2)---[补]

薛定谔方程难

发布于 2024-11-24 08:16:44

3400

代码可运行

文章被收录于专栏：我的C语言我的C语言

运行总次数：0

代码可运行

介绍

这是关于codeforces之旅(2)的补充的部分，补充最后一个D题目的讲解。

1、Sharky Surfing

Sharky Surfing 这题在补题目的时候觉得这个可能是一眼dp，但是读者都知道的，我这个灰名小弱鸡，即使能够想到dp，但是我在想实现的时候发现，这个dp好难实现，我该怎么去寻找一个状态转移方程才能够表示我的状态，这好像比较难得，我有点不会，所以秉持着想15分钟的思路，我看了别人提交的代码。别人的题解几乎都是使用四个数组来存放信息，两个数组分别存放障碍物的起点信息和终点信息，一个数组存放power-up的坐标，还有一个存放提升能力的大小。为了能够尽可能少的次数实现能够跨过所有的地点，我们应该选取能够选取的最大的能力的提升。所以一个priority_queue就是一个存放能力的好方法，在我们的能力坐标小于第一个的障碍物的坐标的时候，我们需要判断当前能力是否能够实现跳过障碍物，如果能的话，就继续向下走直到走到不能跳过的障碍物停止下来，同时存放能够的priority_queue要随着坐标的移动一个一个的存入能力的大小，这样的话能够在需要使用的时候能够选出最大的，同时满足条件的能力提升的大小。如果所有的能力提升都选完并且还跳不过去的话，那么就直接返回-1，不能够实现，如果能够实现的话，就返回加上能力的次数。

#include<iostream>
#include<cstring>
#include<cstdio>
#include <queue>
using namespace std;
const int N = 2e5+10;
int l[N];
int r[N];
int x[N];
int v[N];
priority_queue<int>q;
int solve()
{
    int ret=0,c=1;
    int n,m,L;
    cin>>n>>m>>L;
    for(int i=1;i<=n;i++)
    {
        cin>>l[i]>>r[i];
    }
    for(int i=1;i<=m;i++)
    {
        cin>>x[i]>>v[i];
    }
    while(q.size())q.pop();
    for(int i=1,j=1;i<=n;i++)
    {
        while(j<=m&&x[j]<=l[i])q.push(v[j++]);
        while(q.size()&&c<r[i]-l[i]+2)
        c+=q.top(),q.pop(),ret++;
        if(c<r[i]-l[i]+2)return -1;
    }
    return ret;
}


int main()
{
    int t;cin>>t;
    while(t--)
    {
        printf("%d\n",solve());
    }
}

这样就能够解决问题了。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-11-23，如有侵权请联系 cloudcommunity@tencent.com 删除

queue