Expedition---poj2431(优先队列-堆的实现)

题意：一辆卡车需要行驶 L 距离，车上油的含量为 P，在行驶的过程中有 n 个加油站每个加油站到终点的距离是ai，每个加油站最多给卡车加 b 单位的油；求最后到达终点需要加油的最少次数；如果不能到达，输出-1；

我们可以从起点开始算，看每次油箱中的油是否能够到达下一个加油站，如果不能就加上已经经过的加油站的所能加的最大加油量，如果能到达，就记录一下此加油站可以被加进去；因为我们每次都需要加进去最大的加油

量，所以我们可以用优先队列；来存，那么每次取出来的就是最大值；

时间复杂度是O（n*logn）

用c++中的STL：

#include<stdio.h>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
#define N 101000
#define INF 0xfffffff
using namespace std;

int n, P, L, ans, f;

struct node
{
    int a,b;
} s[N];

int cmp(node n1,node n2)
{
    return n1.a<n2.a;
}

void slove()
{
    priority_queue<int> Q;///优先队列；

    int pos = 0, i = 0;///pos表示当前所在位置；

    while(i <= n)
    {
        int d = s[i].a - pos;

        while(Q.size() && P < d)///当不能到达下一个加油站时，要取出最大的加油量加进去；
        {
            int p = Q.top(); Q.pop();
            P += p;
            ans ++;
        }
        if(P >= d)
        {
            Q.push(s[i].b);
            pos = s[i].a;
            P -= d;
        }
        else
        {
            ans = -1;
            return ;
        }
        i ++;
    }
}

int main()
{
    int i;

    while(scanf("%d",&n) != EOF)
    {
        memset(s, 0, sizeof(s));

        ans=0;

        for(i=0; i<n; i++)
            scanf("%d %d",&s[i].a, &s[i].b);

        scanf("%d %d", &L, &P);

        for(i=0; i<n; i++)
            s[i].a = L - s[i].a;

        s[i].a = L;
        s[i].b = 0;///把终点当成最后一个加油站处理；

        sort(s, s+n+1, cmp);

        slove();

        printf("%d
", ans);
    }
    return 0;
}

View Code

手写实现堆---优先队列；

#include<stdio.h>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
#define N 11000
#define INF 0x3f3f3f3f
using namespace std;


int Max_Heap[N], K;///K代表Max_Heap的个数；
int p;

void Push(int x)///在最大堆中插入x；
{
    Max_Heap[K++] = x;///放到最后一个节点处；

    int t = K-1;

    while(Max_Heap[t] > Max_Heap[t/2] )///当它的值大于它的父节点的值时，要交换一下位置；
    {
        swap(Max_Heap[t], Max_Heap[t/2]);
        t = t/2;
    }
}
void Pop()
{
    K --;///删除元素，堆中总个数减一；
    
    Max_Heap[1] = Max_Heap[K];///把最后一个数放到最上面，然后一步一步往下更新堆；

    Max_Heap[K] = -1;///防止越界，相当于建立哨兵；

    int t = 1;///从第一个节点开始往下更新；

    while( Max_Heap[t] < Max_Heap[t*2] || Max_Heap[t] < Max_Heap[t*2+1])
    {
        if(Max_Heap[t] < Max_Heap[t*2] && Max_Heap[t*2] > Max_Heap[t*2+1])
        {///左儿子大于它时，并且满足左儿子大于右儿子，让左儿子上去；
            swap(Max_Heap[t], Max_Heap[t*2]);
            t = t*2;
        }
        else
        {
            swap(Max_Heap[t], Max_Heap[t*2+1]);
            t = t*2 + 1;
        }
    }
}


int n, P, L, ans, f;

struct node
{
    int a,b;
} s[N];

int cmp(node n1,node n2)
{
    return n1.a<n2.a;
}

void slove()
{
    memset(Max_Heap, -1, sizeof(Max_Heap));

    Max_Heap[0] = INF;

    K = 1;

    int pos = 0, i = 0;

    while(i <= n)
    {
        int d = s[i].a - pos;

        while(K!=1 && P < d)
        {
            int p = Max_Heap[1];
            Pop();
            P += p;
            ans ++;
        }
        if(P >= d)
        {
            Push(s[i].b);
            pos = s[i].a;
            P -= d;
        }
        else
        {
            ans = -1;
            return ;
        }
        i ++;
    }
}

int main()
{
    int i;

    while(scanf("%d",&n) != EOF)
    {
        memset(s, 0, sizeof(s));

        ans=0;

        for(i=0; i<n; i++)
            scanf("%d %d",&s[i].a, &s[i].b);

        scanf("%d %d", &L, &P);

        for(i=0; i<n; i++)
            s[i].a = L - s[i].a;

        s[i].a = L;
        s[i].b = 0;

        sort(s, s+n+1, cmp);

        slove();

        printf("%d
", ans);
    }
    return 0;
}

View Code