题解 CF865D

SJC_03 · 2019-08-13 18:50:39 · 题解

这道题是今天讲课的一道原题，于是蒟蒻突发奇想决定写一篇题解，如有不适还请大佬们轻喷

我的思路是贪心

我们将每天的价格视为一个个"选项"， 压入小根堆中，为了保证买入操作在卖出操作之前，我们从前往后扫描p，对于现在的价格 p_i，如果堆顶元素p_j 满足 p_{j}<p_i ，那么，我们取出堆顶，在第j天买入股票，在第i天卖出股票，此时，我们就可以获得p_i - p_j 的收益

然而，如果之后有p_k 满足p_k > p_i ，辣么，我们当前作出的决策可能并不是最优的，如何反悔呢？

于是，当我们进行上述操作时，我们将p_i也压入堆中，增加一个p_i的选项，弹出时，我们相当于将p_j按照p_i的价格又买了回来

代码如下：

#include <bits/stdc++.h>
using namespace std;

const int maxN = 300001;

int n, pi;
long long ans = 0;

priority_queue< int, vector<int>, greater<int> > Q; \\小根堆

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) { 
        cin >> pi;
        if (!Q.empty() && (Q.top() < pi)) {
            ans += (pi - Q.top());
            Q.pop(); 
            Q.push(pi);
        }
        Q.push(pi);
    }
    cout << ans << endl;
    return 0;
}

同时感谢洛谷，同机房的大佬，以及另一篇题解的作者