Codeforces 853A Planning

题意

给出飞机单位晚点时间代价和原定起飞时间，现在前k分钟不能起飞，求付出的最小代价和起飞顺序

思路

构造两个优先队列q1,q2，q1按时间顺序，q2按代价顺序，初始将所有飞机入q1，将时间在k前的飞机从q1加入q2，然后按时间顺序取出q1加入q2，同时从q2取出代价最大的加入答案

代码

#include<bits/stdc++.h>

using namespace std;

inline int read(){

    int x = ,f= ; char ch = getchar();

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

    while(ch>=''&&ch<='') {x = x*+ch-'';ch = getchar();}

    return x*f;

}

int n, k;

long long ans;

struct F{

    long long t;

    long long v;

    int ans;

    F(){}

    F(int a,int b){

        t = a, v = b;

    }

}f[];

struct CMPT{

    bool operator()(const F& a, const F& b){

        return a.t>b.t;

    }

};

struct CMPV{

    bool operator()(const F& a, const F& b){

        return a.v<b.v;

    }

};

priority_queue<F, vector<F>, CMPT> qt;

priority_queue<F, vector<F>, CMPV> qv;

int main(){

    scanf("%d%d",&n,&k);

    for(int i = ;i<=n;i++) f[i] = F(i, read()), qt.push(f[i]);

    while(qt.top().t<=k && !qt.empty()){

        qv.push(qt.top());

        qt.pop();

    }

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

        if(!qt.empty()) qv.push(qt.top()), qt.pop();

        ans += (i-qv.top().t)*qv.top().v, f[qv.top().t].ans = i;

        qv.pop();

    }

    printf("%I64d\n",ans);

    for(int i = ;i<=n;i++) printf("%d%s",f[i].ans,(i == n?"\n":" "));

    return ;

}