CF865D Buy Low Sell High 题解

· · 题解

题解索引

  1. 题目大意
  2. Solution
  3. AC code
  4. 类似题型

代码类型： C++（cpp）

是否吸氧：否

不压行代码长度：25或25（两种实现方式）

题目大意

题面： <传送门>

题意：给出 n，给出集合 p。

您在第 i 天可以选择花费 p_i 的价格买入一支股票（仅一支），也可以选择在第 i 天以 p_i 的价格卖出一支股票（仅一支），以上两种操作您只能在一天内选一种——当然，您也可以无所事事。初始可以认为您有无限多的金钱，求出您可能获得的最大收益。

术语理解：反悔贪心

Solution

如果我们花费 1 购买了一支股票，有 114514 和 1919810 两种价格可以卖出，我们当然是优先选择后者。可是如果是普通的贪心是做不到这种程度的（也许只我不可）。

于是我们就用“反悔贪心”的方式来解决。为啥叫“反悔贪心”？因为这是我们老师起的因为它在遇到一个更大收益时，优先选择更大的，即反悔次的，选择优的。

首先我们要买入。因为卖出需要买入才行……当栈空时，我们一定要买入（一会我会解答“不操作比买入更赚”的情况）。还有，我们在遇到相对便宜的价格时，也选择买入（这个挺麻烦的，讲到卖就懂了）。

卖出：首先我们要确定，我们遇到了一个价格比买入的物品更贵的，才能卖出，这样才能正收入。还有，我们认为“只有把这个股票卖出时，这个股票才算被买入过”——因为我们反悔的过程中可能更改很多次，所以我们这样认为。然后，我们当遇到一个更大的价格，我们优先选择反悔。如果遇到更小的，我们选择买入。

怎么实现？

维护一个集合，我们称为“目前的操作集合”。

  1. 第一次买入

直接加入集合即可。

  1. 后面的买入

比集合小就入集合（因为卖出才算是买入了，所以无所谓）。

  1. 卖出

我们将卖出为 x 价格认为是 +x，买入 x 价格是 -x。那么，我们可以认为买入了 x，卖出了 y 是 -x+y 。但如果反悔呢？加入我们不选价格 y 了，选了 z，我们按正常思路是这样处理： -x+z。但其实我们并不能这样处理。我们的处理方式是： -x+y-y+z 。为啥呢？因为我们在正常维护时无法找到那个值啊，无法删除啊……

为啥找不到那个值？因为我们每次遇到一个值，是优先跟集合里的最小值比较的，毕竟能挣一点是一点，优先跟最小的比较是最优的。

具体代码流程？

（这里为了方便用 priority_queue 来展示，其实我第一时间想到的是 multiset）

n=read();
while(n--){
    ll x=read();
    if(!q.empty()&&q.top()<x){//栈空一定插入，或者今天的价格比集合内最小值大
        ans+=x-q.top();//赚差价（
        //我们可以认为卖出时也是一种买入，于是就有了这玩意
        q.pop();//要提出队头，因为被反悔了
        q.push(x);//反悔
    }q.push(x);
}

AC code

方法一：multiset 可重集合，自动排序（默认升序）。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<set>
using namespace std;
typedef long long ll;
inline ll read(){
    register int f=1,x=0;register char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}multiset<ll> s;
ll n,ans=0;
int main(){
    n=read();
    while(n--){
        ll x=read();
        if(!s.empty()&&*s.begin()<x){
            ans+=x-*s.begin();
            s.erase(s.begin());
            s.insert(x);
        }s.insert(x);
    }printf("%lld\n",ans);
    return 0;
}

方法二：priority_queue 优先队列，可惜默认大根堆（这也是为啥我优先选择 multiset 的原因）。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<queue>
using namespace std;
typedef long long ll;
inline ll read(){
    register int f=1,x=0;register char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}priority_queue<ll,vector<ll>,greater<ll> >q;
ll n,ans=0;
int main(){
    n=read();
    while(n--){
        ll x=read();
        if(!q.empty()&&q.top()<x){
            ans+=x-q.top();
            q.pop();
            q.push(x);
        }q.push(x);
    }printf("%lld\n",ans);
    return 0;
}

AC 记录1 <传送门>

AC 记录2 <传送门>

类似题型

忘了还有哪道是反悔贪心了（