POJ 2431 Expedition

发布时间：2020-12-14 03:47:58 所属栏目：大数据来源：网络整理

导读：练习优先队列的第一道题题意：一辆卡车需要行驶 $L$ 的距离，卡车油箱里有 $P$ 单位的油，每行驶一单位长度耗费一单位的油，在沿途有 $N$ 个加油站，第 $i$ 个加油站在距离起点 $Ai$ 的位置，可以加 $Bi$ 单位的油，假设油箱容量无限大，最少加多少

练习优先队列的第一道题

题意：

一辆卡车需要行驶 $L$ 的距离，卡车油箱里有 $P$ 单位的油，每行驶一单位长度耗费一单位的油，在沿途有 $N$ 个加油站，第 $i$ 个加油站在距离起点 $Ai$ 的位置，可以加 $Bi$ 单位的油，假设油箱容量无限大，最少加多少次油可以到达终点

样例：

$N = 4,L = 25,P = 10$

$A$ = {10,14,20,21}

$B $= {10,5,2,4}

最少加油次数：2

题解：

使用从大到校的顺序依次取出数值的优先队列，在经过加油站的时候向优先队列里加入 $Bi$,油箱空的时候如果优先队列也是空的那么无法到达，反之取出 $que.top$,给油箱加油

时间复杂度：$O(N*log(N))$

代码：

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
int N,L,P;
int A[maxn],B[maxn];

void solve() {
    A[N] = L;
    B[N] = 0;
    N ++;

    priority_queue<int> que;
    int ans = 0,pos = 0,tank = P;
    for(int i = 0; i < N; i ++) {
        int d = A[i] - pos;
        while(tank - d < 0) {
            if(que.empty()) {
                printf("-1n");
                return ;
            }
            tank += que.top();
            que.pop();
            ans ++;
        }
        tank -= d;
        pos = A[i];
        que.push(B[i]);
    }
    printf("%dn",ans);
}

int main() {
    scanf("%d%d%d",&N,&L,&P);
    for(int i = 0; i < N; i ++)
        scanf("%d%d",&A[i],&B[i]);
    solve();
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!