探险

测试数据来自 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

阶段测试(二)订正

未参加
状态
已结束
规则
OI
题目
6
开始于
2024-03-17 11:00
结束于
2024-04-07 07:00
持续时间
500.0 小时
主持人
参赛人数
14