首页 > 代码库 > poj 2431 expedition

poj 2431 expedition

题目大意:

一辆车开始有n升油,距终点有L km,途中有m个加油站,给出每个加油站到终点的距离与每个加油站可加的油,油箱容量无限大,已知1升油可以使车跑1 km,问最少加多少次油能让车跑到终点。

如果不能到达终点输出-1

 

思路:
模拟加优先队列,一步步看车有没有足够的油跑到下一个加油站,跑到了就把这个加油站能加的油放到优先队列里,没油了就加油,加优先队列的top,然后pop

如果队列空了,还是不到的话就输出-1

需要注意这道题非常坑的是加油站顺序不是给定的,需要排序,因为这个开始wa了

技术分享
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iomanip>
#include<cstdlib>
#include<queue>
#define Maxn 1000005
#define ll long long
#define inf 2147483647
using namespace std;
int ans,t,n,l,p;
struct gs
{
    int b;
    int s;
    bool operator < (const gs &a) const
    {
        if(b<a.b) return true;
        return false;
    }
}ss[Maxn];
int main()
{
    priority_queue <int> q;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&ss[i].b,&ss[i].s);
    }
    scanf("%d%d",&l,&p);
    for(int i=0;i<n;i++)
    {
        ss[i].b=l-ss[i].b;
    }
    ss[n].b=l;
    sort(ss,ss+n);
    for(int i=0;i<=n;i++)
    {
        while(p<ss[i].b-t)
        {
            if(q.empty()) {printf("-1");return 0;}
            p+=q.top();
            ans++;
            q.pop();
        }
        p=p-ss[i].b+t;
        t=ss[i].b;
        q.push(ss[i].s);
    }
    printf("%d",ans);
}
View Code

 

poj 2431 expedition