奶龙过河
422 字
2 分钟
奶龙过河
题目描述
可爱的奶龙面前是一个危险的悬崖通道,它需要使用已有的可悬浮木板安全通过,快来帮帮它吧!
已知通道长为 L,奶龙从起点 0 出发,它有 n 块木板,每块木板分别覆盖一段连续区域 [a, b]。
(题目保证所给木板两两不重合)
- 每块木板最多可使用一次。
- 因为奶龙可以变成奶蛙使腿变长,所以它可以跨过长度不超过 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 30 45 910 12输出
2说明
对于样例1,选用 [0, 4],[5, 9] 这三块木板。
示例2
输入
10 2 10 24 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; }
}文章分享
如果这篇文章对你有帮助,欢迎分享给更多人!




