2016北京集训测试赛（十四）Problem A: 股神小L

Solution

考虑怎么卖最赚钱: 肯定是只卖不买啊(笑)

虽然说上面的想法很扯淡, 但它确实能给我们提供一种思路, 我们能不买就不买; 要买的时候就买最便宜的.

我们用一个优先队列来维护股票的价格, 从前往后扫描. 假设我们已经知道了到前一天的最优策略, 考虑到当前这一天的最优策略: 假如手上还有股票, 那么一定是要把它卖掉的; 假如已经没有股票了, 那么我们就在原本打算卖出的股票以及这一天的股票中选出股价最低的买入. 用优先队列维护股价, 从第一天往后扫描即可.

#include <cstdio>

#include <cctype>

#include <queue>

#include <vector>

#define vector std::vector

#define greater std::greater

#define priority_queue std::priority_queue

namespace Zeonfai

{

    inline int getInt()

    {

        int a = 0; char c;

        while(! isdigit(c = getchar()));

        while(isdigit(c)) a = a * 10 + c - '0', c = getchar();

        return a;

    }

}

const int N = (int)2e5;

int main()

{

    using namespace Zeonfai;

    int n = getInt();

    long long ans = 0;

    static int a[N + 1];

    for(int i = 1; i <= n; ++ i) ans += a[i] = getInt();

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

    for(int i = 1; i <= n; ++ i)

    {

        que.push(a[i]);

        if(que.size() > i >> 1) ans -= que.top() << 1, que.pop();

    }

    printf("%lld\n", ans);

}