题目描述
applepi训练了一个可以自动在股票市场进行量化交易的模型。通常来说,applepi写出的模型,你懂得,就好比一架印钞机。不过为了谨慎起见,applepi还是想先检查一下模型的效果。
applpie收集了“塞帕思股份(surpass)”在最近的连续N天内的价格。在每一天中,他可以做如下事情之一:
1. 睡(把)觉(妹)。
2. 以当天的价格作为成交价买入1股“塞帕思”的股票。
3. 以当天的价格作为成交价卖出1股“塞帕思”的股票。
最初applepi不持有该股票。现在你需要计算出在最优策略下,N天后applepi能够获得的最大利润。
为了维护森林的和平,本着清仓甩锅的原则,在N天的交易结束后applepi也不能持有“塞帕思”的股票。
【输入格式】
每个测试点包含若干组数据,以EOF结尾。对于每组数据:
第一行1个整数N。
第二行N个正整数,相邻两个整数之间用1个空格隔开,表示每一天股票的价格。
【输出格式】
对于每组数据,首先按样例所示的格式“Case #k:”输出该组数据的编号,然后输出一个整数,表示applepi最大能够获得的利润。
【样例】
样例输入1
6
2 6 7 3 5 6
8
1 2 3 4 5 6 7 8
样例输出1
Case #1: 8
Case #2: 16
样例输入2
10
15831 47573 60015 51368 32460 34125 43074 75172 54014 93578
样例输出2
Case #1: 161084
【数据规模与约定】
对于50%的数据,1≤N≤1000。
对于100%的数据,1≤N≤100000,股票价格不超过100000,每个测试点至多包含5组数据。
题解
这是一道经典的贪心问题。
由于最后手上不能剩下股票,所以一次买都会对应一次卖。那么,为了利润最大化,要在最便宜的时候买入,最昂贵的时候卖出。
但是我们没有办法顾及全局的利益,就只能先顾及眼前的利益:
如果当前价格比手上拥有的最低价股票的价格高,即能产生收益,那就以当前价格把它卖出;
反之,如果手上没有股票或者手上拥有的最低价股票的价格比当前价格高,即无法产生收益,那肯定是买入更优,所以就以当前价格买入。
但是,举个反例,如果连续3天的价格分别为2,13,18。那按照这个贪心策略,应该在2的那天买入,在13的那天卖出。但其实在18的那天卖出会更优。
这时候,就不是使用普通贪心了,而应该是反悔贪心。
顾名思义,反悔贪心就是在普通贪心的基础上增添了反悔操作。反悔贪心可以用反悔堆或反悔自动机来维护。这道题用反悔小根堆维护就行了。
那什么时候需要反悔呢?当然是犯了错误的时候啦!
犯错误的情况有两种:
①提前卖出,导致收益减少,即以上反例中的情况;
②本应该买入,却没有买入。
对于第一种情况:
假设在第 \(x\) 天买入,第 \(z\) 天卖出,但在 \(y\) 天提前提前卖出了。其中 \(x < y < z\) 并且 \(a_x \le a_y \le a_z\)。原本的利润应该是 \(a_z - a_x\),但如果提前卖出,利润就变成了 \(a_y - a_x\)。为了补足差价,就可以在第 \(y\) 天再次买入,第 \(z\) 天再次卖出,利润就可以变回 \((a_y - a_x) + (a_z - a_y) = a_z - a_x\)。所以,在第 \(y\) 天提前卖出时,可以将 \(a_y\) 放入堆中,在产生利润时 \((a_z > a_y)\),就会再次卖出,补足差价。
对于第二种情况:
不是没买吗?那就把 \(a_y\) 放入堆中,假装买了就行啦!
AC Code:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
int n;
priority_queue<LL, vector<LL>, greater<LL> > q; // 用优先队列代替堆
int main()
{
int t = 0;
while (~scanf("%d", &n))
{
printf("Case #%d: ", ++ t);
// 初始化
LL ans = 0;
while (!q.empty()) q.pop();
for (int i = 1; i <= n; i ++ )
{
LL x; scanf("%lld", &x);
if (q.empty() || q.top() >= x) // 如果手上没有股票或无法产生收益
q.push(x); // 以当前价格买入
else // 反之
{
ans += x - q.top(); // 以当前价格卖出
q.pop();
q.push(x);
// 多放入堆一次,为了补足差价
q.push(x);
// 多放入堆一次,为了防止没买
}
}
printf("%lld\n", ans);
}
return 0;
}
标签:题解,样例,反悔,买入,量化,卖出,交易,applepi,贪心
From: https://www.cnblogs.com/T-hong/p/18168610