探险
测试数据来自 system/2349
作业已超过截止时间,您无法递交本题目。
时间限制:1秒 内存限制:256M
【问题描述】
一群奶牛租借了一辆卡车决定前往树林里探险,他们每前进一公里的路程就耗费一升的油。为了尽快归还卡车,奶牛们必须前往最近的城市。当前位置和城市间有 \(N\) 个加油站,奶牛可在加油站加油。
对于奶牛来说,树林是个危险的地方,所以奶牛要尽可能的少停站加油。幸运的是,这辆卡卡车的油箱非常大,你可以认为它的容量无限大,卡车离城市 \(L\) 公里时还有 \(P\) 升的油。
你要算出奶牛至少要停几个站才能到城市,或者奶牛们根本到不了城市。
【输入格式】
第一行:单个整数 \(N\),表示加油站的数目。
第二行到第 \(N + 1\) 行:第 \(i + 1\) 行有两个整数 \(X_i\) 和 \(U_i\),\(X_i\) 表示第 \(i\) 个加油站距离城市的距离,\(U_i\) 表示第 \(i\) 个加站最多能加的油量。
第 \(N + 2\) 行:两个整数 \(L\) 和 \(P\),表示汽车在 \(L\) 点时,邮箱中的剩余油量 \(P\) 升。
【输出格式】
单个整数:为达到终点最少停车加油的次数,如果无法到达终点,输出−1。
【输入输出样例】
Input
4
4 4
5 2
11 5
15 10
25 10
Output
2
【输入输出样例解释】
现在卡车距离城市25个公里,卡车里有10升的油。在路上,有4个加油站,分别距离城市4,5,11,15(单位:公里),分别距离卡车起始位置的距离为:21,20,14,10(单位:公里)。这些加油站分别最多可加油4,2,5,10升。
前进10公里,加10升油,再前进4公里,加5升油,就能直接开到终点了。
【数据限制】
对于 \(100\%\) 的数据满足:\(1 ≤ N ≤ 10000\),\(1 ≤ Xi ≤ L; 1 ≤ Ui ≤ 100\),\(1 ≤ P ≤ L ≤ 10^6\)
【来源】
Mr.he