Codeforces 854C(堆+贪心)

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

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

Codeforces Submission

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#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;
}

------ 本文结束 ------