前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Codeforces Round #437 E. Buy Low Sell High(贪心+优先队列)

Codeforces Round #437 E. Buy Low Sell High(贪心+优先队列)

作者头像
Ch_Zaqdt
发布2019-01-11 11:04:41
3980
发布2019-01-11 11:04:41
举报
文章被收录于专栏:Zaqdt_ACM

题目链接:http://codeforces.com/contest/867/problem/E

       题意是给了n个数,表示每天的股票的价格,你可以选择在这天买这个股票或者卖这个股票,或者不买不卖,刚开始你没有股票,最后n天结束后你也没有股票,问能获得的最大价值是多少。

        思路就是用贪心来写,我们肯定要低价买高价卖,所以我们用一个优先队列来维护第i天之前的最便宜的股票,然后找能高价卖出的一天。如果当前天的股票价格低于队首元素的价格,直接让它入队,更新前i天的最低价;当当前天的股票价格高于队首元素的时候,我们可以先将队首最低价格的股票卖掉,那么所得的钱就是x-q.top()。然后将x入队两次,一次代表当前天的股票价格,另一次是对刚刚卖掉的最低股票价格q.top();的维护(因为不一定在当前天卖掉才能获得最大价值,这点不太好理解,模拟一下样例想一下)。因为这些操作是基于卖股票时候得操作,所以当n天过完时不会有剩余。


AC代码:

代码语言:javascript
复制
#include <bits/stdc++.h>
#define ll long long
using namespace std;
priority_queue<int, vector<int>,greater<int> > q;
int n;

int main()
{
	scanf("%d",&n);
	ll ans = 0;
	for(int i=0;i<n;i++){
		int x;
		scanf("%d",&x);
		if(q.empty() || x < q.top())
		{
			q.push(x);
		}
		else
		{
			ans += x - q.top();
			q.pop();
			q.push(x);
			q.push(x);
		}
	}
	cout<<ans<<endl;
	return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018年08月26日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档