AtCoder ABC #250 : G - Stonks

これ系割と苦手。
https://atcoder.jp/contests/abc250/tasks/abc250_g

問題

ある会社の株について、N日間それぞれ、株価が与えられる。
各日には、最大1個株の売買が可能である。

初期状態で株を0個と十分に多くのお金を持っているとき、適切に売買することでN日後にどれだけお金を増やすことができるか。

解法

過去において未購入の株価の情報をmultisetで管理する。
毎日、以下を行う。

• その日の株価Xが、multiset内の金額以下である場合：
  • 過去に株を買い、この日に売る意味はない。よってこの日の株価は、今後の購入に備えmultisetに追加する。
• その日の株価Xが、multiset内の最小金額Y以上である場合：
  • 過去株価Yで株を買い、この日に株価Xで売ることで、差益X-Yを得る。
  • その際、multisetからYを取り除き、Xを2つ追加しよう。これは「株価Xで売ったのを、なかったことにする」「株価Xで買う」と2回分Xを買うことができることに相当する。

int N;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	multiset<ll> cand;
	
	ll ret=0;
	FOR(i,N) {
		cin>>x;
		
		if(cand.size()&&*cand.begin()<x) {
			ret+=x-*cand.begin();
			cand.erase(cand.begin());
			cand.insert(x);
		}
		cand.insert(x);
	}
	cout<<ret<<endl;
	
	
}

まとめ

株価の問題、過去にもいろいろあったけど、このパターン触れたことなかったかな…。