[ CodeForces 865 D ] Buy Low Sell High
2024-10-01 01:05:15
\(\\\)
\(Description\)
给出\(N\)天股票的价钱\(A_1,...,A_N\),每天可以什么都不做,或者买入或卖出\(1\)支股票,分别花出或收入\(A_i\)元,求最大收益。
- \(N\in [1,3\times10^5]\),\(A_i\in [1,10^6]\)
\(\\\)
\(Solution\)
贪心,显然每天的一支股票只有两种选择,这种情况下通常用堆去维护当前最优代价,问题是如何消去交换的影响。
具体地说,首先有一个简单的思路就是,按时间顺序将价格插入一个小根堆,如果当前价格大于堆顶或堆为空就买堆顶,如果小于就插入堆中。这种做法看似正确,实际上在遇到相邻两两配对买入卖出的数据中,在一个奇数位置放一个非常大的数就可以卡掉。
然后就有了一个想法,每次卖出时,我们都是取出堆顶,然后用当前价格减掉堆顶累计答案。而如果想用更高的价钱卖出这一支股票,就要将低价的股票不在这一次卖出。而这个转换可以使用区间拼合的方式,即我们先用当前的价格卖出这一支股票,并将当前卖出价格放进堆中,如果这个数再次被选到,代表用新的价格卖出之前的那支股票,即:高卖出价与低卖出价的差价\(+\)低卖出价与买入价的差价\(=\)高卖出价与买入价的差价。
而我们发现只这么做并不严谨。因为替换之后相当于中间价并没有被使用,而在这一过程中中间价消失了,不会再作为买入价出现。为了避免这个情况,我们每次卖出的时候,都将卖出的价格插入堆中两次,一次代表作为中转价格转手给更高的卖出价,另一次代表转手之后这个点作为买入价。
\(\\\)
\(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;
}
最新文章
- 如何避免git每次提交都输入密码
- MyBatis中关于别名typeAliases的设置
- Ubuntu菜鸟入门(一)—— 截图工具安装
- equals标准写法
- Emgu学习之(四)——图像阈值
- 【leetcode】Word Ladder
- exports 和 module.exports 的区别
- CSS阻止页面双击选中文本
- 编译基于ARM LINUX的驱动模块的Makefile
- FZU 2150 Fire Game(BFS)
- View和ViewGroup的区别 -- Touch事件处理
- JS 匿名函数 自执行
- 制作一个vagrant的win7 box
- 修改 Sublime 按快捷键 ctrl+s 自动格式化(reindent lines)的问题
- CF 741D. Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths [dsu on tree 类似点分治]
- springMVC 使用ajax 出现No serializer found for class异常
- SpringBoot-目录及说明
- hibernate入门一
- c# chart控件柱状图,改变柱子宽度
- 【sping揭秘】16、@After(finally) 但是这个实在afterturning之前执行
热门文章
- 【04】AngularJS&#160;表达式
- MongoDB增加用户、删除用户、修改用户读写权限及只读权限(注:转载于http://www.2cto.com/database/201203/125025.html)
- [K/3Cloud]屏蔽页签的关闭按钮
- XOR的艺术
- 【BZOJ3676&;UOJ103】回文串(manacher,Trie)
- Nginx 重写规则指南1
- 如何修改ICO文件的尺寸
- iOS常用的正则表达式总结
- swift 2.0 语法 可选类型
- 【转】 vsftp上传文件出现553 Could not create file解决方法