poj2431 Expedition （优先队列） 挑战程序设计竞赛

题目链接：http://poj.org/problem?id=2431

Description

Input

Output

Sample Input

4
4 4
5 2
11 5
15 10
25 10

Sample Output

2

Hint

因为求得是最优解，需要尽可能少的加油站，所以我们每次希望去加油的时候 加最大的那个，因而将加油站push进priority_queue(堆结构，默认每次弹出最大值)

从起点开始跑，把路程通过加油站分成几部分，每一部分只要通过加油能到达加油站即可，，因而，把终点也视为加油站 距离L，加油量 0；

#include<cstdio> //输入量较大，所以用c风格来输入输出， ac时间 16ms ， 全部换成c++的风格则需要 313ms
#include<queue>
#include<algorithm>
using namespace std;
struct node{
	int a1,b1;
};
int cmp(const node& a,const node& b){
	return a.a1<b.a1;
}
int main(){
	priority_queue<int> pq;
	int n;
	node no[10010];
	while(scanf("%d",&n)!=EOF){
		for(int i=0;i<n;i++){
			scanf("%d%d",&no[i].a1,&no[i].b1);
		}
		int L,P,cnt=0,sign=0;
			scanf("%d%d",&L,&P);
		for(int i=0;i<n;i++){  //题目要求给的a1是当前与终点的距离，我们转换为与起点的距离
			no[i].a1=L-no[i].a1;
		}
		sort(no,no+n,cmp);
		int index=0;
		//pq.push(P);
		int pos=0;
		no[n].a1=L;  //将终点设为加油站
		no[n].b1=0;
		n++;
		for(int i=0;i<n;i++){
			 int d=no[i].a1-pos; //当前需要走的距离
			 while(P<d){  
				 if(pq.empty()){ //油箱为空
					 puts("-1");
					 sign=1;
					 break;
				 }
				 else{
					 P+=pq.top();
					 pq.pop();
					 cnt++;
				 }
			 }
			 P-=d;
			 pos=no[i].a1;
			 pq.push(no[i].b1);
		}
		if(!sign){
			printf("%d\n",cnt);
		}
		
	}
	return 0;
}

下面是另一种方法

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
struct node{
	int a1,b1;
}no[10010];
int cmp(const node&a, const node&b){
	return a.a1<b.a1;
}
int main(){
	int t;
	priority_queue<int>pq;
	while(scanf("%d",&t)!=EOF){
		while(!pq.empty())
			pq.pop();
		for(int i=0;i<t;i++){
			scanf("%d%d",&no[i].a1,&no[i].b1);
		}
		int l,p;
		scanf("%d%d",&l,&p);
		for(int i=0;i<t;i++){
			no[i].a1=l-no[i].a1;
		}
		sort(no,no+t,cmp);
		int cur=p;//当前位置
		int i=0;
		int cnt=0;
		while(cur<l){ //如果还没到终点 
			while(no[i].a1<=cur&&i<t){ //能加油就尽量加
				pq.push(no[i].b1);
				i++;
			}
			if(pq.empty()) break;
			cur+=pq.top(); 当前位置往前移动 （加上当前最大的加油站里的油）
			pq.pop();
			cnt++;
		}
		if(cur>=l) //当最远跑的距离超过终点
			printf("%d\n",cnt);
		else
			printf("-1\n");
	}
	return 0;
}

poj2431 Expedition （优先队列） 挑战程序设计竞赛

原文：http://blog.csdn.net/chaiwenjun000/article/details/47290747