Codeforces Round #437 (Div. 1)D Buy Low Sell High（贪心+优先队列/multiset）

Buy Low Sell High

time limit per test: 2 seconds
memory limit per test: 256 megabytes

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·10^5$), the number of days.

Following this is a line with exactly N integers $p_1, p_2, ..., p_N(1 ≤ p_i ≤ 10^6)$. 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.

链接

http://codeforces.com/contest/866/problem/D

题意

给定n个数字表示接下来n天的的股价，每天可以选择买一份股票，卖一份股票或者什么都不做，最开始拥有零份股票，有足够多的钱，问n天之后能获得的最大收益。

题解

思考一个问题，怎么才能获得收益？当然是低价买入高价卖出，但是问题是如果现在就卖出了后面可能会有更高的价格可以卖出。怎么解决这个问题呢？

我们可以用一个优先队列（从小到大排序）代表当前所持有的所有股票，枚举每个时候的股票价格，如果队首元素值小于当前枚举值，那么就可以卖出股票赚取利润，队首元素出队，但是注意需要把当前枚举值再次加入队列，因为被弹出的队首元素可能会和后面价格更高股票交易获取更多的利润，可以用当前枚举值与后面价格更高的股票交易，相当于当前枚举的股票没有进行操作。A买入B卖出，B买入C卖出等价于A买入C卖出，相当于B没有操作。比如2 5 9，5-2=3+9-5=4= 9+5-(5-2)=7。

具体参见代码，有两种写法，升序优先队列priority_queue <ll, vector <ll>, greater <ll> > Q;和可重复集合multiset <ll> S。

写法一
- Accepted 140 ms 6200 KB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <set>
#include <algorithm>
typedef long long ll;
using namespace std;

int main()
{
    int n;
    ll x, ans = 0;
    priority_queue <ll, vector <ll>, greater <ll> > Q;
//    scanf("%d", &n);
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        scanf("%lld", &x);
        Q.push(x);
        if (Q.top() < x)
        {
            ans += x - Q.top();
            Q.pop();
            Q.push(x);
        }
    }
//    printf("%lld\n", ans);
    cout << ans << endl;
    return 0;
}

写法二
- Accepted 234 ms 9600 KB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <set>
#include <algorithm>
typedef long long ll;
using namespace std;

int main()
{
    int n;
    ll x, ans = 0;
    multiset <ll> S;
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        scanf("%lld", &x);
        S.insert(x);
        if (*S.begin() < x)
        {
            ans += x - *S.begin();
            S.erase(S.begin());
            S.insert(x);
        }
    }
    cout << ans << endl;
    return 0;
}

看上去multiset比优先队列更费内存和时间。

The end.
2018-08-27 星期一