首页 > 代码库 > 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); }
poj 2431 expedition
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。