POJ 2431 Expedition(プライオリティキュー)
1690 ワード
タイトルリンク:
http://poj.org/problem?id=2431
タイトル:
1本の道にはn個のガソリンスタンドがあり、終点から起点までの距離はLであるが、n個のガソリンスタンドから終点までの距離はa[i]であり、各ガソリンスタンドは自動車にb[i]のガソリンを加えることができる.
最少何回プラスしてゴールに着くことができて、ゴール出力-1に着くことができません.
分析:
少なくとも私たちはもうすぐなくなる時に給油して、それから毎回一番多い油を入れるべきです.
そこで私たちがi番目のガソリンスタンドを通ったとき、b[i]を優先列に入れて到着できなかったとき
現在の位置に到達するまで1つずつ取り出し、キューが空で現在に到達できない場合は移動できません.
位置は永遠に達成できない.
コードは次のとおりです.
http://poj.org/problem?id=2431
タイトル:
1本の道にはn個のガソリンスタンドがあり、終点から起点までの距離はLであるが、n個のガソリンスタンドから終点までの距離はa[i]であり、各ガソリンスタンドは自動車にb[i]のガソリンを加えることができる.
最少何回プラスしてゴールに着くことができて、ゴール出力-1に着くことができません.
分析:
少なくとも私たちはもうすぐなくなる時に給油して、それから毎回一番多い油を入れるべきです.
そこで私たちがi番目のガソリンスタンドを通ったとき、b[i]を優先列に入れて到着できなかったとき
現在の位置に到達するまで1つずつ取り出し、キューが空で現在に到達できない場合は移動できません.
位置は永遠に達成できない.
コードは次のとおりです.
#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 1000010;
struct stop {
int a,b;
bool operator <(const struct stop &tmp)const {
return a<tmp.a;
}
} p[maxn];
int n,l,pp;
void solve()
{
p[n].a=l,p[n].b=0;
sort(p,p+n+1);
int tot = pp;
priority_queue<int >Q;
while(!Q.empty()) Q.pop();
int ans = 0,pos=0,tag=0;
for(int i=0; i<=n; i++) {
int dis = p[i].a-pos;
while(tot<dis) {
if(Q.empty()) {
printf("-1
");
return;
}
tot+=Q.top();
Q.pop();
ans++;
}
tot-=dis;
pos=p[i].a;
Q.push(p[i].b);
//printf("tot: %d
",tot);
}
printf("%d
",ans);
return ;
}
int main()
{
while(~scanf("%d",&n)) {
int a,b;
for(int i=0; i<n; i++)
scanf("%d%d",&p[i].a,&p[i].b);
scanf("%d%d",&l,&pp);
for(int i=0; i<n; i++)
p[i].a=l-p[i].a;
solve();
}
return 0;
}
/***
4
4 4
5 2
11 5
15 10
25 10
***/