51nod K 汽油补给 大根堆+小根堆....

题目传送门

用优先队列瞎搞... 想着在每个地方 先算上一个点到这一个点要花费多少钱 这个用小根堆算就好 然后在这个地方加油 把油钱比自己多的替代掉 这个用大根堆维护一下 然后两个堆之间信息要保持互通 这个有点麻烦 我用的f数组维护 这样就好了 中间懒得改全部开了long long 不要介意

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#include<iostream>

#define LL long long

using namespace std;

const int M=;

LL read(){

    LL ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

LL n,k;

struct node1{//小根堆

    LL h,w,pos;

    bool operator<(const node1&x)const{return w>x.w;}

};

priority_queue<node1>q1;

struct node2{//大根堆

    LL h,w,pos;

    bool operator<(const node2&x)const{return w<x.w;}

};

priority_queue<node2>q2;

LL old,cnt,tot;

bool f[*M];

int main()

{

    LL l,w,now;

    n=read(); k=read(); cnt=n;

    l=read(); w=read();

    q1.push((node1){k,w,}),q2.push((node2){k,w,}); old=l;

    for(int i=;i<=n;i++){

        l=read(); w=read(); LL h=old;

        if(l>k){printf("-1\n"); return ;}

        while(old){

            node1 x=q1.top(); now=x.h;// printf("[%d %d]\n",x.h,x.w); //system("pause");

            if(f[x.pos]){q1.pop(); continue;}

            if(now>old) tot=tot+old*x.w,q1.pop(),q1.push((node1){now-old,x.w,++cnt}),q2.push((node2){now-old,x.w,cnt}),f[x.pos]=,old=;

            else if(now==old) tot=tot+now*x.w,f[x.pos]=,q1.pop(),old=;

            else tot=tot+now*x.w,f[x.pos]=,q1.pop(),old-=now;

        }

        q2.push((node2){h,w,i}),q1.push((node1){h,w,i});

        LL ans=k-old,sum=;

        while(ans){

            node2 x=q2.top(); now=x.h;

            if(f[x.pos]){q2.pop(); continue;}

            if(x.w<=w) break;

            if(ans>=now) sum+=now,q2.pop(),f[x.pos]=,ans-=now;

            else sum+=ans,ans=,q2.pop(),f[x.pos]=,q2.push((node2){now-ans,x.w,++cnt}),q2.push((node2){now-ans,x.w,cnt});

        }

        if(sum) q2.push((node2){sum,w,++cnt}),q1.push((node1){sum,w,cnt});

        old=l;

    }

    while(old){

        node1 x=q1.top(); now=x.h;

        if(f[x.pos]){q1.pop(); continue;}

        if(now>old) tot=tot+old*x.w,q1.pop(),q1.push((node1){now-old,x.w,++cnt}),q2.push((node2){now-old,x.w,cnt}),f[x.pos]=,old=;

        else if(now==old) tot=tot+now*x.w,f[x.pos]=,q1.pop(),old=;

        else tot=tot+now*x.w,f[x.pos]=,q1.pop(),old-=now;

    }

    printf("%lld\n",tot);

    return ;

}