[ CodeForces 865 D ] Buy Low Sell High

\(\\​\)

\(Description\)

---

给出\(N\)天股票的价钱\(A_1,...,A_N\)，每天可以什么都不做，或者买入或卖出\(1\)支股票，分别花出或收入\(A_i\)元，求最大收益。

• \(N\in [1,3\times10^5]\)，\(A_i\in [1,10^6]\)

\(\\\)

\(Solution\)

---

• 贪心，显然每天的一支股票只有两种选择，这种情况下通常用堆去维护当前最优代价，问题是如何消去交换的影响。

• 具体地说，首先有一个简单的思路就是，按时间顺序将价格插入一个小根堆，如果当前价格大于堆顶或堆为空就买堆顶，如果小于就插入堆中。这种做法看似正确，实际上在遇到相邻两两配对买入卖出的数据中，在一个奇数位置放一个非常大的数就可以卡掉。

• 然后就有了一个想法，每次卖出时，我们都是取出堆顶，然后用当前价格减掉堆顶累计答案。而如果想用更高的价钱卖出这一支股票，就要将低价的股票不在这一次卖出。而这个转换可以使用区间拼合的方式，即我们先用当前的价格卖出这一支股票，并将当前卖出价格放进堆中，如果这个数再次被选到，代表用新的价格卖出之前的那支股票，即：高卖出价与低卖出价的差价\(+\)低卖出价与买入价的差价\(=\)高卖出价与买入价的差价。

• 而我们发现只这么做并不严谨。因为替换之后相当于中间价并没有被使用，而在这一过程中中间价消失了，不会再作为买入价出现。为了避免这个情况，我们每次卖出的时候，都将卖出的价格插入堆中两次，一次代表作为中转价格转手给更高的卖出价，另一次代表转手之后这个点作为买入价。

\(\\\)

\(Code\)

---

#include<cmath> #include<queue> #include<cstdio> #include<cctype> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define R register #define gc getchar using namespace std; typedef long long ll;inline int rd(){int x=0; bool f=0; char c=gc();while(!isdigit(c)){if(c=='-')f=1;c=gc();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}return f?-x:x; }priority_queue<int> q;int main(){int n=rd();ll res=0;for(R int i=1,x;i<=n;++i){x=rd();if(q.size()&&x>-q.top()) res+=(ll)x+q.top(),q.pop(),q.push(-x);q.push(-x);}printf("%lld\n",res);return 0; }

转载于:https://www.cnblogs.com/SGCollin/p/9683088.html

总结

以上是生活随笔为你收集整理的[ CodeForces 865 D ] Buy Low Sell High的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。