用优先队列瞎搞... 想着在每个地方 先算上一个点到这一个点要花费多少钱 这个用小根堆算就好 然后在这个地方加油 把油钱比自己多的替代掉 这个用大根堆维护一下 然后两个堆之间信息要保持互通 这个有点麻烦 我用的f数组维护 这样就好了 中间懒得改全部开了long long 不要介意
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<iostream> #define LL long long using namespace std; const int M=11100007; LL read(){ LL ans=0,f=1,c=getchar(); while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); 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[2*M]; int main() { LL l,w,now; n=read(); k=read(); cnt=n; l=read(); w=read(); q1.push((node1){k,w,1}),q2.push((node2){k,w,1}); old=l; for(int i=2;i<=n;i++){ l=read(); w=read(); LL h=old; if(l>k){printf("-1 "); return 0;} while(old){ node1 x=q1.top(); now=x.h;// printf("[%d %d] ",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]=1,old=0; else if(now==old) tot=tot+now*x.w,f[x.pos]=1,q1.pop(),old=0; else tot=tot+now*x.w,f[x.pos]=1,q1.pop(),old-=now; } q2.push((node2){h,w,i}),q1.push((node1){h,w,i}); LL ans=k-old,sum=0; 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]=1,ans-=now; else sum+=ans,ans=0,q2.pop(),f[x.pos]=1,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]=1,old=0; else if(now==old) tot=tot+now*x.w,f[x.pos]=1,q1.pop(),old=0; else tot=tot+now*x.w,f[x.pos]=1,q1.pop(),old-=now; } printf("%lld ",tot); return 0; }