低买高卖(CF865D)题解

本文主要是介绍低买高卖(CF865D)题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意描述

已知接下来 $n$ $(1\leqslant n\leqslant 3\cdot 10^5 )$ 天股票价格，你每天可以买入一股，卖出一股，或者不做任何操作，求收益最大值。

解题思路

1.动态规划

容易想到这种dp算法。设 $f_{i,j}$ 表示在第 $i$ 天持有 $j$ 股时手里最多的钱。对于 $j=0$ ，可以由卖出或不操作得到；对于 $j>0$ ，可由买入、卖出以及不做操作得到。

于是状态转移方程 $f_{i,j}=\left\{\begin{matrix}max\left \{ f_{i-1,j},f_{i-1,j+1}+a_i\right \}(j=0) \\ max\left \{ f_{i-1,j},f_{i-1,j+1}+a_i,f_{i-1,j-1}-a_i\right \}(j>0) \end{matrix}\right.$

时间复杂度 $O(n^2)$ ，滚动数组优化后空间复杂度 $O(n)$ 。

明显无法通过，但没有办法优化dp算法，于是我们换一个思路。

2.反悔贪心

一般的贪心思想是这样的：每一天如果前面有比当天价格小的，在能买的且价格最小的那天买入一股并在这天卖出。

但是这个思路有问题，比如下面这组数据

3
1 2 3

根据刚才的思路，我们会在第2天发现第1天价格低，于是在第1天买入股票并在第二天卖出，第3天不进行操作。但事实上，第1天买入并在第3天卖出会优于这种方案。

于是就要让贪心能够“反悔”。

注意到如果对股票买了又卖，相当于没有操作。所以可以把卖出的股票价格也放入候选之中（当然，每天的价格都会放入候选，表示以在当天买入，所以卖出的股票价格会被加入候选两次）。那么后面从候选中选择这天股票的意义

被选择0次，这天卖出股票。
被选择1次，这天不进行操作，
被选择2次，这天买入股票，被假设为这天卖出的股票在后面的一天卖出。

用堆维护候选中最小价格。

时间复杂度 $O(nlog_n)$ ，空间复杂度 $O(n)$ 。

示例代码

#include<bits/stdc++.h>using namespace std;typedef long long LL;const int N=3e5+5;int n;
LL a[N];
priority_queue<LL,vector<LL>,greater<LL> > pq;
LL res;int main()
{scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);for(int i=1;i<=n;i++){if(!pq.empty()&&pq.top()<a[i]){res+=a[i]-pq.top();pq.pop();pq.push(a[i]);}pq.push(a[i]);}printf("%lld\n",res);return 0;
}