https://www.cnblogs.com/Miracevin/p/9686577.html
已知接下來N天的股票價格,每天你可以買進一股股票,賣出一股股票,或者什么也不做.N天之后你擁有的股票應為0,當然,希望這N天內能夠賺足夠多的錢.
輸入:
第一行一個整數天數N(2<=N<=300000).
第二行N個數字p1,p2...pN(1<=pi<=10^6),表示每天的價格.
輸出: N天結束后能獲得的最大利潤.
題解
非常經典的貪心問題
用一個優先佇列小根堆，
假設每個股票都買入，
當前的股票價格>堆頂的時候，把這個股票加進去兩次，然后彈出堆頂，
否則加進去一次，
把這個差價計入ans，ans+=price[i]-q.top()
什么意義呢？
首先，我們雖然假設都買入，但是并不一定都買，
我們只有在計算差價的時候，相當于才會把某個價格買入，再以price[i]賣出，
而我們把這個股票加進去兩次，
一次是正常的假設買入，為了之后可能賺取差價，
另一次是為了反悔，
假設股票價格是：3 7 10
最優解是3買入，10賣出，賺7元
也就是說，我以3價格買入，但我會在7元的時候賣出，
但是7元賣可能不是最優秀的，
所以，我們把7元再加進去，當輪到10元的時候，這個7元會再當做一個股票賣出ans+=10-7
發現，有意思的是，10-3=(10-7)+(7-3)
這就相當于3元買入，10元賣出，7元這天摸魚，
如果10后面假設還有一個20
即3,7,10，20
那么，我們10元之后，佇列里有7，10,10
20元會7元買入，20元賣出，相當于7元這天買入了一股，
這樣下去，我們總能把最少的價格買入，盡量多的價格賣出，
如果不是最優秀的話，就不買不賣了，就是最后優先佇列里剩下的一些，就是預定買入，但是實際沒有買入的部分，
#include<bits/stdc++.h> using namespace std; const int N=300000+10; int n; int p[N]; priority_queue<int,vector<int>,greater<int> >q; long long ans; int main() { scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&p[i]); q.push(p[i]); if(!q.empty()&&q.top()<p[i]) { ans+=p[i]-q.top(); q.pop(); q.push(p[i]); } }printf("%lld",ans);return 0; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/139446.html
標籤：其他
上一篇：演算法天天練系列匯總
下一篇：啟發式演算法