首页 > 代码库 > poj 2431 Expedition 贪心+最大堆
poj 2431 Expedition 贪心+最大堆
当油量不够时从走过的油站中选最大加油量的
#include<iostream> #include<queue> #include<stdlib.h> #include<algorithm> using namespace std; #define MAX_N 10005 struct node{ int dist,fuel; }t[MAX_N]; bool cmp(const node &a,const node &b) { return a.dist<b.dist; } int L,P; int N; int main() { priority_queue<int> que; cin>>N; for(int i=0;i<N;i++) cin>>t[i].dist>>t[i].fuel; cin>>L>>P; for(int i=0;i<N;i++) t[i].dist = L-t[i].dist; sort(t,t+N,cmp); t[N].dist=L;//将终点看成加油量为0的加油站 t[N].fuel=0; N++; int cur=P;//当前油量 int dis=0; int ans=0; for(int i=0;i<N;i++) { int d = t[i].dist-dis; while(cur-d<0) { if(que.empty()) { puts("-1"); return 0; } cur += que.top(); que.pop(); ans++; } cur -= d; dis=t[i].dist; que.push(t[i].fuel); } cout<<ans<<endl; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。