[2015普及组-D]推销员 思维que

题：https://www.cometoj.com/problem/0221

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
const int M=1e5+5;
struct node{
    int len,id,a;
    bool operator<(const node &b)const{
        
        return 2*len+a<b.len*2+b.a;
    }
};
priority_queue<node>que;
int S[M];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&S[i]);
    }
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        node p;
        p.id=i;
        p.len=S[i];
        p.a=x;
        que.push(p);
    }
    int  ans=0ll,nowlen=0;;
    for(int i=1;i<=n;i++){
        node p;
        while(!que.empty()&&max(S[que.top().id]-nowlen,0)<que.top().len){
            p=que.top();
            que.pop();
            p.len=max(S[p.id]-nowlen,0);
            que.push(p);
        }
        p=que.top();
        que.pop();
        if(S[p.id]>nowlen){
            ans+=(S[p.id]-nowlen)*2;
            nowlen=S[p.id];
        }
        ans+=p.a;
        printf("%d
",ans);
    }
    return 0;
}