(￣▽￣") 没钱了

TimeLimit: 1000ms  MenoryLimit:65536KB

64-bit integer IO format:

%lld

Problem Description

在忙碌的假期中, BOBO学长在考完驾驶证后，决定开车去旅游，然而，他不想经常的停下车，来给小车加油，他想尽快到达旅游点，在行驶的途中想要尽量少次数的给小车加油。 

他行驶的道路是一条笔直的公路，在这条公路上，有 N (1 <= N <= 10,000) 个加油站，第i个加油站位于

距离旅游点L[i]单位距离的地方，并且能够提供P[i]的汽油。 

现在，他距离他的旅游点为L单位距离，并且此时小车有着P(1 <= P <= 1,000,000)升单位的汽油。 

*假定他的小车比较高端，可以无限容纳汽油。 

*结果及其中间结果均在int范围内。 

*每向前行驶1单位距离消耗1单位汽油. 

输入的第i个加油站距离旅游点的位置不是有序的。 

滚来滚去……~(～o￣▽￣)～o 。。。滚来滚去……o～(＿△＿o～) ~。。。

Input

第一行，输入N，表示有N个加油站。 

第2~N+1行，每行输入两个数值L[i]和P[i],分别表示每个加油站的距离旅游点位置L[i]单位距离和最多能加P[i]升的汽油。 

第N+2行输入L和P，分别表当前位置距离旅游点L单位距离和小车最开始时有P单位汽油。

Output

问小车从起点到终点最少要加几次油？若，在小车无法到达终点，则输出-1。

 

SampleInput

44 45 211 515 1025 10

SampleOutput

2

题意：

　　　第一行，输入N，表示有N个加油站。

　　　第2~N+1行，每行输入两个数值L[i]和P[i],分别表示每个加油站的位置L[i]和最多能加P[i]升的汽油。

　　　第N+2行输入L和P，分别辆卡车要行驶L单位距离和卡车最开始时有P单位汽油。

　　　每向前行驶1单位距离消耗1单位汽油,起点,终点,以及加油站是在同一条直线上的,卡车的油箱无限大，无论加多少油都没问题。

        问小车从起点到终点最少要加几次油？若，在小车无法到达终点，则输出-1。

分析：

　　 起点和终点是一条直线，这条直线上有若干个加油站能够提供加油，最少需要加多少次油才能到达终点。

　　 要使得加油的次数最少的话，则是尽可能的让小车的没油的时候，才去加油站加汽油。

      对于小车来说，每次当经过第i个加油站的时候，能够选择加油或者不加，也就是在之后的路程中可以使用或者不使用这些汽油。

      所以，我们每次把经过的加油站时，所能够提供的每份汽油保存起来，在下次汽油不足的时候，才去取出来，每次先前保存下来的那份最多的汽油，再继续行驶，在判断。从而可以得出需要最少加油的次数。

　　

代码：（优先队列+贪心）

1 #include 
         
           2 #include 
          
            3 #include 
           
             4 #include 
            
              5 #include 
             
               6 using namespace std; 7 struct Node{
       int L,P;}; 8 struct CMP_L{
       bool operator()(Node a,Node b){
       return a.L
              
               ,CMP_L>ID_L;17 priority_queue
               
                
                 ,CMP_P>ID_P;18 for(i=0;i