视频加载失败

奶龙过河

422 字
2 分钟
奶龙过河

题目描述#

可爱的奶龙面前是一个危险的悬崖通道,它需要使用已有的可悬浮木板安全通过,快来帮帮它吧!

已知通道长为 L,奶龙从起点 0 出发,它有 n 块木板,每块木板分别覆盖一段连续区域 [a, b]。

(题目保证所给木板两两不重合)

  1. 每块木板最多可使用一次。
  2. 因为奶龙可以变成奶蛙使腿变长,所以它可以跨过长度不超过 k 的空隙(木板与木板,木板与地面,地面与地面)。

请你给出奶龙所需要的木板的最少数量。

输入描述#

第一行输入三个整数 L, n, k。(1 <= L <= 10^4, 1 <= n <= 10^3, 0 <= k <= 10^3) 接下来 n 行,每行输入两个整数 a_i, b_i,表示第 i 块木板所覆盖的区间 [a_i, b_i]。(0 <= a < b <= 10^4)

输出描述#

输出一个整数,代表奶龙所需要的木板的最少数量。若无法安全走过悬崖,则输出 -1。

示例1#

输入

12 3 3
0 4
5 9
10 12

输出

2

说明

对于样例1,选用 [0, 4],[5, 9] 这三块木板。

示例2#

输入

10 2 1
0 2
4 6

输出

-1

说明

对于样例2,无论怎么选择都无法通过悬崖。

备注#

无

我的代码#

#include <bits/stdc++.h>
using namespace std;
struct board
{
int a;
int b;
};
bool cmp(const board& x,const board& y)
{
return x.b>y.b;
}
int main ()
{
int l,n,k;
cin>>l>>n>>k;
vector <board> x(n);
for(int i=0;i<n;i++)
{
cin>>x[i].a>>x[i].b;
}
sort(x.begin(),x.end(),cmp);
int st=0;
int ans=0;
int p=0;
while (st+k<l&& p==0)
{
int temp;
for(int i=0;i<n;i++)
{
temp = st;
if(st+k>=x[i].a)
{
st=x[i].b;
ans++;
break;
}
}
if(st==temp)
{
cout<<"-1";
p=1;
}
}
if(p==0)
{
cout<<ans;
}
}

文章分享

如果这篇文章对你有帮助,欢迎分享给更多人!

奶龙过河
https://www.xiaobaibai454.top/posts/study-26-11-04/
作者
Xiao_baibai
发布于
2026-11-04
许可协议
CC BY-NC-SA 4.0

评论区

Profile Image of the Author
Xiao_baibai
你是怎么找到这里的???
分类
最新动态
站点统计
文章
25
分类
4
标签
5
总字数
17,871
运行时长
0 天
最后活动
0 天前
站点信息
构建平台
GitHub Actions
博客版本
Firefly v6.16.8
文章许可
CC BY-NC-SA 4.0
文章目录