题解：SP348 EXPEDI - Expedition

代码调不出来，先看看有没有初始化，包括答案和堆。是谁没清空我不说。

显然如果在一个加油站选择停车，那么肯定要把加油站的油都偷走买走。

因为限制只有停车次数，所以加油时选择油量更大的加油站。

把已经到达的加油站存起来，如果到不了后面的加油站，那么在走过且没加油的加油站中选择油量最大的加油，直到能到下一个加油站。

如果走过的所有加油站都加了油，但还是到不了下一个加油站，则无解。

具体处理方面，我们用堆维护可加油的加油站，设 f 为当前能到达的位置，即 f=l-p。每到达一次加油站，维护一次 l 和 p。每加一次油，维护一次 p 和答案。f 每时每刻都更新。此外，终点我们也当做一个加油站处理。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
#define reg register
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
    char c=getchar();ll x=0,f=1;
    while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
ll m,n,l,p,f,ans=0,T;
struct node{
    ll a,b;
}z[N];
struct cmp{
    inline bool operator()(const node x,const node y)
    {
        return x.b<y.b;
    }
};
priority_queue<node,vector<node>,cmp> da;
inline bool cmpa(const node x,const node y)
{
    return x.a>y.a;
}
int main()
{
    T=read();
    while(T--)
    {
        while(!da.empty())//务必清空 
        {
            da.pop(); 
        }
        memset(z,0,sizeof z);
        ans=0;
        n=read();
        for(int i=1;i<=n;i++)
        {
            z[i].a=read();
            z[i].b=read(); 
        }
        n++;
        z[n].a=0;
        z[n].b=0;//将终点也作为一个加油站 
        l=read();
        p=read();
        sort(z+1,z+n+1,cmpa);//按位置排序 一个一个走 
        bool flag=1;
        for(int i=1;i<=n;i++)
        {
            f=l-p;
            while(f>z[i].a&&!da.empty())//加油 
            {
                node x;
                x=da.top();
                da.pop();
                p+=x.b;
                ans++;
                f=l-p;
            }
            if(f<=z[i].a)//能到就放到堆里 到不了就无解 
            {
                da.push(z[i]);
            }
            else
            {
                cout<<-1;
                flag=0;
                break;
            }
            p=p-l+z[i].a;
            l=z[i].a;
            f=l-p;
            if(f<=0)//可以直接走到终点 
            {
                cout<<ans;
                flag=0;
                break;
            }
        }
        if(flag) cout<<ans;
        cout<<"\n";
    }
    return 0;
}