CodeForces 865D Buy Low Sell High

  • 2018-08-25
  • 39
  • 1

D. Buy Low Sell High

题目:

You can perfectly predict the price of a certain stock for the next N days. You would like to profit on this knowledge, but only want to transact one share of stock per day. That is, each day you will either buy one share, sell one share, or do nothing. Initially you own zero shares, and you cannot sell shares when you don’t own any. At the end of the N days you would like to again own zero shares, but want to have as much money as possible.

Input:

Input begins with an integer N (2 ≤ N ≤ 3·105), the number of days.
Following this is a line with exactly N integers p1, p2, …, pN (1 ≤ pi ≤ 106). The price of one share of stock on the i-th day is given by pi.

Output

Print the maximum amount of money you can end up with at the end of N days.

Sample Input:

9
10 5 4 7 9 12 6 2 10

Sample Output:

20

Sample Input:

20
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4

Sample Output:

41

题目链接

题目给出一串数字p[i]代表股票在时间i时的价格,可以在任意时刻以p[i]价格购入股票或者抛售股票,求可以获取的最大利润(可以同时持有多股)。

假设买入所有股票,维护一个升序优先队列代表第i个时间之前持有的所有股票,枚举每个时刻的股票价格,若队首值小于枚举值则可以在当前枚举时间抛售股票以赚取利润,用当前枚举股票价格减队首股票价格是两次操作一次买卖可赚取的利润,加入结果,弹出队首元素,再向队列中添加一个枚举股票价格(因为在现在枚举时刻以现在的价格卖出后队首元素被弹出,可能那个队首元素可以和后面的更高股票价格结合赚取更多的利润,所以添加现在股票价格,若后面数列中有更高的股票价格则可以用现在的枚举价格和更高的股票价格结合赚取利润,相当于现在枚举的股票价格没有操作,是队首股票价格和后面的更高股票价格结合赚取利润)。

AC代码:

评论