\(\\?\)

\(Description\)

---

給出\(N\)天股票的價(jià)錢\(A_1,...,A_N\)，每天可以什么都不做，或者買入或賣出\(1\)支股票，分別花出或收入\(A_i\)元，求最大收益。

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

\(\\\)

\(Solution\)

---

• 貪心，顯然每天的一支股票只有兩種選擇，這種情況下通常用堆去維護(hù)當(dāng)前最優(yōu)代價(jià)，問(wèn)題是如何消去交換的影響。

• 具體地說(shuō)，首先有一個(gè)簡(jiǎn)單的思路就是，按時(shí)間順序?qū)r(jià)格插入一個(gè)小根堆，如果當(dāng)前價(jià)格大于堆頂或堆為空就買堆頂，如果小于就插入堆中。這種做法看似正確，實(shí)際上在遇到相鄰兩兩配對(duì)買入賣出的數(shù)據(jù)中，在一個(gè)奇數(shù)位置放一個(gè)非常大的數(shù)就可以卡掉。

• 然后就有了一個(gè)想法，每次賣出時(shí)，我們都是取出堆頂，然后用當(dāng)前價(jià)格減掉堆頂累計(jì)答案。而如果想用更高的價(jià)錢賣出這一支股票，就要將低價(jià)的股票不在這一次賣出。而這個(gè)轉(zhuǎn)換可以使用區(qū)間拼合的方式，即我們先用當(dāng)前的價(jià)格賣出這一支股票，并將當(dāng)前賣出價(jià)格放進(jìn)堆中，如果這個(gè)數(shù)再次被選到，代表用新的價(jià)格賣出之前的那支股票，即：高賣出價(jià)與低賣出價(jià)的差價(jià)\(+\)低賣出價(jià)與買入價(jià)的差價(jià)\(=\)高賣出價(jià)與買入價(jià)的差價(jià)。

• 而我們發(fā)現(xiàn)只這么做并不嚴(yán)謹(jǐn)。因?yàn)樘鎿Q之后相當(dāng)于中間價(jià)并沒有被使用，而在這一過(guò)程中中間價(jià)消失了，不會(huì)再作為買入價(jià)出現(xiàn)。為了避免這個(gè)情況，我們每次賣出的時(shí)候，都將賣出的價(jià)格插入堆中兩次，一次代表作為中轉(zhuǎn)價(jià)格轉(zhuǎn)手給更高的賣出價(jià)，另一次代表轉(zhuǎn)手之后這個(gè)點(diǎn)作為買入價(jià)。

\(\\\)

\(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; }

轉(zhuǎn)載于:https://www.cnblogs.com/SGCollin/p/9683088.html

總結(jié)

以上是生活随笔為你收集整理的[ CodeForces 865 D ] Buy Low Sell High的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。