题目传送门
题意:一辆卡车要行驶L长度,初始有P油,每行驶一个单位长度消耗一单位油。有n个加油站可以加油,问最少加油几次才能行驶L长度,如果不能输出-1
分析:按照挑战书的解法,每走到一个加油站相当于获得一次加油的权利,等到油没有的时候再选择之前可加油的站的最大油量加上,可以用优先队列高效得到最大值,如果队列里没油使得继续前进则为-1
收获:换一种思考方式,加上高效的数据结构能完美解决难题
/************************************************
* Author :Running_Time
* Created Time :2015/9/14 星期一 08:28:25
* File Name :POJ_2431.cpp
************************************************/
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std;
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e4 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
struct Oil {
int p, v;
bool operator < (const Oil &r) const {
return p < r.p;
}
}o[N];
int main(void) {
int n;
while (scanf ("%d", &n) == 1) {
int L, P;
for (int i=n; i>=1; --i) scanf ("%d%d", &o[i].p, &o[i].v);
scanf ("%d%d", &L, &P);
for (int i=n; i>=1; --i) o[i].p = L - o[i].p; //起点到加油站的距离
o[++n].p = L; o[n].v = 0;
sort (o+1, o+1+n);
priority_queue<int> Q;
int ans = 0, pos = 0;
for (int i=1; i<=n; ++i) {
int d = o[i].p - pos;
P -= d;
while (P < 0) {
if (Q.empty ()) {
ans = -1; break;
}
P += Q.top (); Q.pop ();
ans++;
}
if (ans == -1) break;
pos = o[i].p;
Q.push (o[i].v);
}
printf ("%d\n", ans);
}
return 0;
}
编译人生,运行世界!