Codeforces 854C(堆+贪心)

Codeforces 854C
题意：有n架飞机，第i架飞机原本计划在第i分钟起飞，可是由于某种原因整个机场前k分钟是不能起飞的，每分钟只能起飞一架飞机，然后告诉你每架飞机每延误一分钟会造成的损失，问你如何安排飞机的起飞时间才能将损失降到最少（飞机不能提前起飞）。

把所有飞机的延迟时间按照当前时间一一插入，然后每次起飞就飞延迟时间大的那个，因为越往后拖越损失大。

Codeforces Submission

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
struct data {
    int no, c;
    bool operator < (const data &b) const {
        return c < b.c;
    }
};
int n, k, sc[300000 + 5];
priority_queue<data> q;
void clean() {
}
void solve() {
    clean();
    LL ans = 0;
    for (int i = 1; i <= n + k; i++) {
        if (i <= n) {
            int x; scanf("%d", &x);
            q.push((data){i, x});
        }
        if (i > k) {
            data p = q.top(); q.pop();
            ans += (LL)p.c * (LL)(i - p.no);
            sc[p.no] = i;
        }
    }
    printf("%I64d\n", ans);
    for (int i = 1; i <= n; i++) printf("%d ", sc[i]);
}
int main() {
    scanf("%d%d", &n, &k), solve();
    return 0;
}