Expedition

直接中文

Descriptions

一群奶牛抓起一辆卡车，冒险进入丛林深处的探险队。作为相当差的司机，不幸的是，奶牛设法跑过一块岩石并刺破卡车的油箱。卡车现在每运行一个单位的距离泄漏一个燃料单位。

为了修理卡车，奶牛需要沿着一条蜿蜒的长路行驶到最近的城镇（距离不超过1,000,000个单位）。在这条路上，在城镇和卡车的当前位置之间，有N（1 <= N <= 10,000）燃料站，奶牛可以停下来获得额外的燃料（每站1..100个单位）。

丛林对人类来说是一个危险的地方，对奶牛尤其危险。因此，奶牛希望在前往城镇的路上尽可能少地停下燃料。幸运的是，他们的卡车上的油箱容量非常大，实际上它可以容纳的燃油量没有限制。卡车目前距离城镇L单位，有P单位的燃料（1 <= P <= 1,000,000）。

确定到达城镇所需的最小停留次数，或者奶牛根本无法到达城镇。

Input

*第1行：单个整数，N

*行2..N + 1：每行包含两个以空格分隔的整数，用于描述燃料停止：第一个整数是从城镇到停靠点的距离; 第二个是该站点可用的燃料量。

*行N + 2：两个以空格分隔的整数，L和P.

Output

*第1行：一个整数，给出到达城镇所需的最少燃料停留次数。如果无法到达城镇，则输出-1。

Sample Input

Sample Output

Hint

输入细节：

卡车距离城镇25个单位; 这辆卡车有10个燃料单位。沿着这条路，距离城镇4,5,11和15的距离有4个燃料站（所以这些距离最初距离卡车的距离为21,20,14和10）。这些燃料停止装置可分别提供多达4个，2个，5个和10个单位的燃料。

输出细节：

驱动10个单位，停止再购买10个单位的燃料，再开4个单位，停止再购买5个单位的燃料，然后开车到镇上。

题目链接

https://vjudge.net/problem/POJ-2431

假如我经过一个加油站，我就获得了加这个站的油的权利，那么我可以一直走，一直走到没油，这时候取出我前面能加的油里面最多的那个加上继续走，讲这些加油站放入优先队列即可

AC代码

#include <iostream>

#include <cstdio>

#include <fstream>

#include <algorithm>

#include <cmath>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <cstring>

#include <map>

#include <stack>

#include <set>

#include <sstream>

#define IOS ios_base::sync_with_stdio(0); cin.tie(0);

#define Mod 1000000007

#define eps 1e-6

#define ll long long

#define INF 0x3f3f3f3f

#define MEM(x,y) memset(x,y,sizeof(x))

#define Maxn 100000+5

using namespace std;

struct node

{

    int dis;//距离

    int value;//油

    bool operator<(const node &c)const//按距离从大到小排序

    {

        return dis>c.dis;

    }

};

node a[Maxn];

priority_queue<int>q;

int L,P,N;

int main()

{

    cin>>N;

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

        cin>>a[i].dis>>a[i].value;

    cin>>L>>P;

    sort(a,a+N);//排序

    q.push(P);

    int ans=,i=;

    while(L>&&!q.empty())

    {

        ans++;//用了几个加油站

        L-=q.top();

        q.pop();

        while(i<N&&L<=a[i].dis)//L<=a[i].dis,即进过加油站，存入队列

        {

            q.push(a[i].value);

            i++;

        }

    }

    if(L>)

        cout<<-<<endl;

    else

        cout<<ans-<<endl;//第一次的油是自己的

    return ;

}

巴特西

【POJ - 2431】Expedition（优先队列）

Expedition

最新文章

热门文章