题目:

考虑股票市场，一共有n天。
对于第i天，B君知道股票的价格是每单位a[i]元
在每一天，B君可以选择买入一个单位的股票，卖出一个单位的股票，或者什么都不做。
刚开始B君有无穷多的钱，但是没有任何股票。
问n天之后B君最多可以赚多少钱。
(1 <= n <= 200000)
(1 <= a[i] <= 10000)

输入

第一行一个整数n表示天数。
接下来一行n个整数，表示每天的价钱。

输出

一行一个整数表示最多可以赚的钱数。
输入样例

1 2	9 10 5 4 7 9 12 6 2 10

输出样例

题解：

利用优先队列建立最小堆，遍历时，每次首先push当前a[i]两次，取堆中的最小值，若堆中最小值为a[i]，相当于未进行操作。
下面解释一下为何要push两次
1.堆里面存储的值，相当于已经买的股票，因此第一次push可以认为购买了当天的股票。
2.从堆中取出最小值之后，ans加上当前a[i]与堆中最小元素的差值，此时第二次push的a[i]可以认为是堆中最小元素的一个跳板，以备以后出现利润更高的天数。
例子：1 3 9
day1: <1,1> <1> ans = 0
day2: <1,3,3> <3,3> ans = 2
day3: <3,3,9,9> <3,9,9> ans = 2+9-3 = 8
根据上述例子，我们可以看到在第三天时，取到了堆中最小的元素3，此时的元素3是由元素1变化而来的，最终的ans为8，即1->3 3->9 ,可以认为1->9 即第一天买入，第二天不进行操作，第三天卖出。而当第三天结束时，我们可以看到仍有一个元素3存在，这就是假设购入了第二天的股票，以备后面的进行比较。
第二个例子：1 3 9 10
day1：<1,1> <1> ans = 0
day2:<1,3,3> <3,3> ans = 2
day3:<3,3,9,9> <3,9,9> ans = 8
day4：<3,9,9,10,10> <9,9,10,10> ans = 15
可以看出在day2结束时<3,3> 一个为元素1转化而来，一个为元素3，分别在day3，day4被选取。

代码：

#include<stdio.h>
#include<set>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn = 200010;
int a[maxn];
priority_queue<int> s;
int main()
{
    int n;
    scanf("%d", &n);
    long long ans = 0;
    for(int i = 0; i < n; i++){
        scanf("%d", &a[i]);
        s.push(-a[i]);
        s.push(-a[i]);
        ans += a[i] + s.top();
        s.pop();
    }
    printf("%lld\n", ans);
}

huring

51nod-2206-低买高卖

题目:

输入

输出

题解：

代码：