POJ 2431 Expedition

題意：
　　一群牛從起點要出發到城鎮(目的地)距離共L單位，每走一單位同時消耗一單位的油，一開始油箱有P單位的油量，路途中會經過幾個加油站，每個加油站會給兩個數字，1.距離城鎮多少單位，2.這個加油站能加多少油，本題問到目的最少要到幾個加油站加油，如果不可能到達目的地則輸出-1。

想法：
　　因為所有地點都在同一直線上，所以都會經過每個加油站，只是看要不要停下來加油而已。所以我們就盡可能往前走，把每個路過加油站的該站的加油量放到priority queue裡面，然後直到走到途中沒油了，就從priority queue裡面拿出第一個(最大的加油量)加到自己的油箱，因為既然要加油，就要一次加最多的油，一直反覆這個動作直到終點。

	#include <cstdio>
	#include <algorithm>
	#include <queue>
	using namespace std;
	struct fuel_stop{
	int pos;
	int amount;
	}stop[10010];
	bool cmp(fuel_stop a, fuel_stop b)
	{
	return a.pos > b.pos;
	}
	int main()
	{
	int N, L, P;
	while (scanf("%d", &N) != EOF) {
	for (int i = 0; i < N; ++i)
	scanf("%d %d", &stop[i].pos, &stop[i].amount);
	scanf("%d %d", &L, &P);
	sort(stop, stop + N, cmp);
	stop[N] = {0,0}; // 終點也當一個stop
	priority_queue<int> PQ; // PQ用來裝每個stop的油量
	int dis = L - stop[0].pos; // 起點~第一站
	int sum_dis = dis; // 總共已經走了多遠
	P -= dis;
	int i = 0; // i用來當index
	int ans = 0;
	bool OK = 1;
	while (sum_dis < L && OK) {
	while (P >= 0) { //當身上油還>=0時繼續前進
	dis = stop[i].pos - stop[i+1].pos;
	P -= dis;
	sum_dis += dis;
	PQ.push(stop[i].amount);
	++i;
	if (i == N) break;
	}
	while (P < 0 && OK) { // PQ裡面從最多油量開始挑,加入油箱
	if (PQ.empty()) OK = 0;
	else{
	P += PQ.top();
	PQ.pop();
	++ans;
	}
	}
	}
	if (OK) printf("%d\n", ans);
	else puts("-1");
	}
	}

view raw [POJ] 2431 Expedition.cpp hosted with ❤ by GitHub