poj 2431，poj

poj 2431，poj

大意：

　　有n個加油點，給出每個加油點距離終點的位置和能加多少油，最後一行給出總長度和最初的油量。求最少加幾次油能到終點，不能到的話輸出-1.

Sample Input

4
4 4
5 2
11 5
15 10
25 10

Sample Output

2

分析：

　　一開始打算用dfs搜索，用dis[i]代表到i點時能加的油量，dfs(i,p,l),i代表當前位置，p代表當前油量，l代表總長，當i+p>=l時，這種情況符合條件，得每種能成立情況的加油次數再取最小值就好，但超時.

　　於是想到用優先隊列，能以目前的油量跑得越遠，加油次數越少。所以優先隊列裡存放油量，用pre代表之前的位置，用rest代表當前油量，dis代表走多遠，每走過一個點rest-=dis,把這個點的油量存入優先隊列中，當rest<dis時從隊列中取元素。沒元素可取就意味著不能到終點。

代碼：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
struct point
{
    int x,y;
}s[10010];
bool cmp(point a,point b)
{
    return a.x<b.x;
};
int main()
{
    int n;
    cin>>n;
    int i;
    for(i=0;i<n;i++)
        cin>>s[i].x>>s[i].y;
    int l,p;
    cin>>l>>p;
    for(i=0;i<n;i++)
        s[i].x=l-s[i].x;
    sort(s,s+n,cmp);
    s[n].x=l;
    s[n].y=0;
    priority_queue<int>q;
    int rest=p;
    int pre=0;
    int ans=0;
    for(i=0;i<n+1;i++)
    {
        int dis=s[i].x-pre;
        while(rest<dis)
        {
            if(q.empty())
            {
                 ans=-1;
                 break;
            }
            rest+=q.top();
            q.pop();
            ans++;
        }
        if(ans==-1)
            break;
        rest-=dis;
        pre=s[i].x;
        q.push(s[i].y);

    }
    cout<<ans<<endl;
}