【优先队列-贪心】问题集合

  • 中间商优化

http://codeforces.com/problemset/problem/867/E

一个长度为N的序列,代表每天股票的价格,每天只能执行 买/卖/无动作 三种操作。问如何才能赚得最多。

维护一个优先队列,队首存当前最小的价格,见到比最小的价格高的就先卖掉,并且把低价股票的价格变成当前价格,更低的就进队。如果以后遇到更高的可以和交易过的股票交易,也可以和没交易过的股票交易,它们赚的钱是一样的。。经过xyjj的指点知道了这类题的做法叫中间商优化,先找到更高的卖了提升价格,以后可以继续交易。

#include<iostream>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<vector> 
#include<utility>
using namespace std;
typedef long long ll;
priority_queue<ll,vector<ll>,greater<ll> > b;

ll n,t;
ll ans=0;
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&t);
		b.push(t);
		if(b.top()<t)
		{
			ans+=t-b.top();
			b.pop();
			b.push(t);
		}
	}
	printf("%lld",ans);
}

 … Read the rest