(￣▽￣") 没钱了

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

SampleOutput

题意：

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

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

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

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

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

分析：

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

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

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

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

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

 #include <iostream>

 #include <stdio.h>

 #include <queue>

 #include <vector>

 #include <algorithm>

 using namespace std;

 struct Node{int L,P;};

 struct CMP_L{bool operator()(Node a,Node b){return a.L<b.L;}};

 struct CMP_P{bool operator()(Node a,Node b){return a.P<b.P;}};

 int main()

 {

     int N,i,j,L,P,Begin,Dic,Times;

     Node NUM;

     while(scanf("%d",&N)!=EOF)

     {

         priority_queue<Node,vector<Node>,CMP_L>ID_L;

         priority_queue<Node,vector<Node>,CMP_P>ID_P;

         for(i=;i<N;i++)

         {

             scanf("%d%d",&NUM.L,&NUM.P);

             ID_L.push(NUM);

         }

         scanf("%d%d",&L,&P);

         NUM.L=;NUM.P=;

         ID_L.push(NUM);

         Begin=L;Times=;

         while(!ID_L.empty())

         {

             NUM=ID_L.top();ID_L.pop();

             Dic=Begin-NUM.L;

             while(P-Dic<)

             {

                 if(ID_P.empty())

                 {

                     Times=-;

                     break;

                 }

                 P+=ID_P.top().P;

                 ID_P.pop();

                 Times++;

             }

             if(Times==-)break;

             P-=Dic;

             Begin=NUM.L;

             ID_P.push(NUM);

         }

         printf("%d\n",Times);

     }

     return ;

 }