codeforce 867E 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 begins with an integer N (2 ≤ N ≤ 3·10⁵), the number of days.

Following this is a line with exactly N integers p₁, p₂, ..., p_N (1 ≤ p_i ≤ 10⁶). The price of one share of stock on the i-th day is given by p_i.

Output

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

Examples

Input

9
10 5 4 7 9 12 6 2 10

Output

Input

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

Output

Note

In the first example, buy a share at 5, buy another at 4, sell one at 9 and another at 12. Then buy at 2 and sell at 10. The total profit is - 5 - 4 + 9 + 12 - 2 + 10 = 20.

题目意思：知道股票每一天的价格，每天可以选择买入或者卖出股票，而且只能操作一次当我们手中没有股票的时候不可以出售，问最后所能获得的最大价值。

思路：考虑用优先队列（小顶堆）维护这一过程，我们每次得到一个新的价格，将其和堆顶的价格比较，如果比堆顶的价格低，就直接放入堆中，如果比堆顶的价格高，就意味着我们可以提前以堆顶的价格买入一个物品，然后以当前价格卖出，因此我们可以算出本次收益加到总收益中。

不过这里存在一个问题，比如：

例子： 2 5 9 7
将2压入队列，由于5>2，卖出，队顶2清除（升序优先队列取队列中最小元素放置队顶），差价为3。可是第三天可以卖9块钱，这样第二天不卖，第三题才卖的话，差价为7，赚得更多。
这里看到别的文章给出了一个思路，如果5>2，则2出队，压入两次5：
第一次压入5：
真正意义上地买下了 2 ，出售的价格为 N（此时只卖到 5 ），其买入2后出售的总盈利sum+=N - 2，此时N等于 5 （N为最后真正需要出售的价格，即这例子中的 9 ，只不过现在只遍历到了 5 ），sum已经等于了 5-2=3 。这时 2 出队，5 进队，相当于2被5所替换掉（买入的2升值为 5 ）。这样做会使得：即便之后，9>5（此时5为队顶元素），5出队，sum+= 9-5，此时sum仍为9。这是因为相当于：将2卖到9分成两部分了，先将2卖到5，再将5卖到9，其总差值是不变的。这样做就可以保证了 2 卖到 9 ！

所以两次压入的
第二次压入5
是为了：假设我这次也是买，看看后面有没有比5大的【当然这时队列中有两个 5 ，逻辑上一个是为了卖掉 2 那只（即本例中的 9 - 2），如果之后还有比5大的，那么就购买这里的 5 ，那边卖掉（即本例中的 7 - 5）。当然即使9与7对调sum也是不变的】。如果只有一个比5大的（即没有7），那么相当于只用了 9 买了 2 ；如果没有一个大于5的（即只有 2 5），那么相当于只用了 5 买了 2 。
当然如果当前num并未大于队顶元素的话，就假设买下它，同时也就是加入队列中。因为如果之后还有大于num的股价且这时候num成为了队顶，那么就要买它了；如果不需要用到它即遍历完了后，它还不是队顶（即会有比它还小的股价，买入这个更小的）；或者之后没有一个股价大于它，那就不操作它（不然就赔了）

如同上面所述，这样循环式地到第N个数判断完后，sum就是最大盈利值了

所以两次压入的作用就是

1.做中间价

2.做所有可能买入价中的一个（就和比堆顶低的价格直接扔入堆中一样的作用）

代码：

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

priority_queue<int, vector<int>, greater<int> >q;  

int main()
{
	int n,m;
	while(cin>>n) {
		long long sum = 0;
		if(!q.empty()) {   //循环清除队列令其初始化
			q.pop();
		}
		while(n--) {
			scanf("%d",&m);
			if(!q.empty() && m > q.top()) {  //一定要先判空再比较，不然如果队列是空的话直接比较程序会崩
				sum += m-q.top();
				q.pop();
				q.push(m);
				q.push(m);
			}
			else{
				q.push(m);
			}
		}
		cout<<sum<<endl;
	}
	return 0;
}