斑羚飞渡

[编程题]斑羚飞渡

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

题目背景

两个人之间只能有一个活着 ,这必然是我和你的战争——Harry Potter

题目描述

水宝宝在看完《斑羚飞渡》这本书后，突发奇想，想到了一个有趣的问题

现在峡谷的这边有n只斑羚，每只斑羚跳跃的最远距离为x[i],斑羚在别人的背上起跳的最远距离为y[i],峡谷的两岸的距离为s，问在最好情况下，有几只斑羚可以用别人的背当跳板跳到对岸，但由于斑羚的先天原因(主要是太肥)，只能把别人当跳板一次

注:本系列题不按难度排序哦

输入描述:

输入格式：

第一行n,s 接下来n行，每行2个整数代表x[i],y[i]

输出描述:

输出格式：

一行一个整数，表示有几只斑羚可以用别人的背当跳板跳到对岸

示例1

输入

输出

说明

第一组是第三只斑羚跳6的距离，第一只斑羚跳6的距离后从第三只的背上起跳，再跳8的距离后到达对岸

第二组是第五只跳2的距离，第二只跳2的距离后从第五只的背上起跳,跳100的距离到达对岸(假设对岸无限长，不可能跳出对岸)

备注:

对于100%的数据，n<=1000000;

对于所有数据，s<=1000000000; x[i],y[i]<=s; 不保证x[i]<y[i]

算法知识视频讲解

WDgaster

发表于 2022-03-08 14:52:49

对于任意两个斑羚而言，如果它们都可以单独越过，可以确定这两个斑羚的最大贡献是二，如果一个可以单独越过，可以确定这两个斑羚的最大贡献是一，如果两个都不能单独越过，那么如果可以贡献1的价值，一定是一只通过另一只实现飞过，那么为了确保可以踩，一定是在一只斑羚跳到了最大值时踩，为了确保可以踩过，一定是y更大展开全文