[贪心]Zexal的浩瀚星辰-2018级算法C3-E题解

发表于 | 分类于 | 热度: 度

题目链接

本题是一道经典的贪心问题，考虑两个火箭 i 和 j，在两个火箭均可发射时，若 i 的损失费 p[i] 大于 p[j]，且 i 在 j 之后发射，两个火箭的损失费之和
$$
cost_1 = p[i] \cdot (t[i] - i) + p[j] \cdot (t[j] - j)
$$
若交换两个火箭发射顺序，则两个火箭的损失费之和
$$
cost_2 = p[i] \cdot (t[j] - i) + p[j] \cdot (t[i] - j)
$$
作差得
$$
\begin{aligned}
cost_1-cost_2 &= p[i] \cdot (t[i] - t[j]) + p[j] \cdot (t[j] - t[i]) \&= (p[i] - p[j]) \cdot (t[i] - t[j])
\end{aligned}
$$
又 $p[i] > p[j]$，$t[i] > t[j]$，所以 $cost_1 > cost_2$，即对于已经可以发射的两个火箭，损失费较大的火箭先发射所产生的损失费最小。

由以上证明可以看出，本题中在当前可以发射的火箭中，损失费较大的火箭应该排在前面，同时还要考虑到火箭从当前不可发射到当前可以发射的状态转换，所以可以使用一个优先队列来维护当前可以发射的火箭集合，每次弹出损失费最大的火箭，将损失费加入答案，并放入新增的可以发射的火箭。

同时，由数据范围不难发现运算过程中使用 int 会导致溢出。

代码如下：

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
40
41
42
43
44
45
46
47
48
#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;

const int N = 500000 + 5;

struct Rocket {
    long long price, index;

    bool operator<(const Rocket &b) const {
        return price < b.price || (price == b.price && index < b.index);
    }
} rockets[N];

priority_queue<Rocket> PQ;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k, p;
    while (cin >> n >> k) {
        long long ans = 0;

        for (int i = 1; i <= n; i++) {
            cin >> p;
            rockets[i].price = p;
            rockets[i].index = i;

            if (i <= k)
                PQ.push(rockets[i]);
        }

        for (int i = k + 1; i <= k + n; i++) {
            if (i <= n)
                PQ.push(rockets[i]);

            Rocket tmp = PQ.top();
            PQ.pop();

            ans += tmp.price * (i - tmp.index);
        }

        cout << ans << endl;
    }
    return 0;
}