首页 > 代码库 > POJ2431 Expedition(排序+优先队列)
POJ2431 Expedition(排序+优先队列)
思路:先把加油站按升序排列。
在经过加油站时,往优先队列里加入B[i].(每经过一个加油站时,预存储一下油量)
当油箱空时:1、如果队列为空(可以理解成预存储的油量),则无法到达下一个加油站,更无法到达目的地。
2、否则就取出队列里的最大元素,来给汽车加油(贪心思想)
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; int n,l,p; int t[10005]; struct Node { int a,b; bool operator < (const Node e)const { return e.a>a; } }s[10005]; int B[10005]; int A[10005]; int main() { //freopen("d:\\test.txt","r",stdin); cin>>n; priority_queue<int>q; for(int i=0;i<n;i++) { scanf("%d%d",&t[i],&s[i].b); } cin>>l>>p; for(int i=0;i<n;i++) { s[i].a=l-t[i]; } sort(s,s+n); for(int i=0;i<n;i++) { A[i]=s[i].a; B[i]=s[i].b; } A[n]=l;B[n]=0; int pos=0,fuil=p,ans=0; for(int i=0;i<=n;i++) { int d=A[i]-pos; while(fuil<d) { if(q.empty()) {cout<<"-1";return 0;} fuil+=q.top(); q.pop(); ans++; } fuil-=d; pos=A[i]; q.push(B[i]); } cout<<ans<<endl; return 0; }
POJ2431 Expedition(排序+优先队列)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。