POJ_2431 Expedition 【数据结构】

一、题面

POJ2431

二、分析

主要说几个坑

1.给出的点需要根据下标排序。

2.根据不同的方式要把起始点或者终点加进去。我没有转换距离，而是直接从起始点到终点根据距离不断相减判断的，那么起点就是25，所以要把终点0加进去。如果转换距离的话，终点就是相对于出发点25。这个根据个人选择。

三、AC代码

#include <cstdio>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

struct Node
{
    int l, p;
    bool operator<(const Node t)const
    {
        return l > t.l;
    }
}Data[10003];
int N, L, P;

void solve()
{
    int ans = 0, next = L-P;
    priority_queue<int> pq;
    
    for(int i = 0; i < N; i++)
    {
        while(Data[i].l < next)
        {
            if(pq.empty())
            {
                printf("-1
");
                return;
            }
            next = next - pq.top();
            pq.pop();
            ans++;
        }
        pq.push(Data[i].p);
    }
    printf("%d
", ans);
}
int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    while(scanf("%d", &N)!=EOF)
    {
        for(int i = 0; i < N; i++)
        {
            scanf("%d %d", &Data[i].l, &Data[i].p);
        }
        scanf("%d %d", &L, &P);
        Data[N].l = 0, Data[N].p = 0;
        N++;
        sort(Data, Data+N);
        solve();
    }
    return 0;
}