首页 > 其他分享 >【题解】 量化交易5

【题解】 量化交易5

时间:2024-04-30 20:55:38浏览次数:28  
标签:题解 样例 反悔 买入 量化 卖出 交易 applepi 贪心

题目描述

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

相关文章

  • Educational Codeforces Round 165 (Rated for Div. 2) 题解
    A对于\(i\top_i\)连边。如果存在二元环,则答案为2。否则答案为3。B非降序排序:0全部在1前面。令0的个数为z。从左往右,将前z个全部填上0。填第\(i\)位时,每次填的最小代价为:若第\(i\)位为1,第\(i\)位右边的第一个0到\(i\)之间的字符个数。(贪心)......
  • 【题解】 量化交易4
    题目描述applepi训练了一个可以自动在股票市场进行量化交易的模型。通常来说,applepi写出的模型,你懂得,就好比一架印钞机。不过为了谨慎起见,applepi还是想先检查一下模型的效果。applpie收集了“塞帕思股份(surpass)”在最近的连续N天内的价格。在每一天中,他可以做如下事情之一:......
  • 【题解】 量化交易3
    题目描述applepi训练了一个可以自动在股票市场进行量化交易的模型。通常来说,applepi写出的模型,你懂得,就好比一架印钞机。不过为了谨慎起见,applepi还是想先检查一下模型的效果。applpie收集了“塞帕思股份(surpass)”在最近的连续N天内的价格。在每一天中,他可以做如下事情之一:......
  • CF1765C Card Guessing 题解
    考虑期望的线性性,求每种情况猜对的概率和,最终再除掉\({4n\choosen,n,n,n}\)。考虑枚举最少的出现次数\(mn\),记四种卡的出现次数分别为\(c_1,c_2,c_3,c_4\),\(c_1+c_2+c_3+c_4=i\lek\),则这种情况的方案数为:\[{i\choosec_1,c_2,c_3,c_4}{4n-i\choosen-c_1,n-c_2,n-c_3,n-c_......
  • 题解 CF1965E【Connected Cubes】
    场切了1E,第一次上IGM,纪念一下。多图警告。我们称题目中的一个方块为“某色混凝土”。感受一下,发现本题主要的难点在于这些混凝土方块排布得太紧密了,导致容易出现互相遮挡的现象,进而难以构造。于是,我们先思考能否通过一些操作使得这些混凝土互相分离。如下图的方式可以将每两......
  • CF1956F Nene and the Passing Game 题解
    题目链接点击打开链接题目解法首先答案为连边之后连通块的个数把限制中的\(i,j\)分开,则\(i,j\)能传球当且仅当\(i+l_i\lej-l_j\)且\(j-r_j\lei+r_i\)这是一个二维偏序的形式先考虑怎么暴力做,考虑将\((i+l_i,0),\;(i-l_i,1)\)排序,然后按顺序加入如果碰到操作\(......
  • npm下载包时报错 Unexpected token '.'问题解决
    1.出现问题当通过nvm切换nodejs版本为16以上时,npminstall[package]报错:Unexpectedtoken'.'2.问题原因该问题不是npm的问题,也不是nodejs的问题,是nvm-windows的问题。3.解决问题nvm-windows已经更新版本解决了这个问题我是通过更新nvm-windows到版本1.19解决了这个问题......
  • Atcoder ABC 351 全题解
    乾岩我:G题来咯!!!大火:这G题,大家都不敢做,说是有人在里面放了毒瘤。我:做,做,为什么不做!不做也别想活着!!!(两天后)我:我的G题完成辣!!!!!!AB不讲C显然$2^a*2=2^{a+1}$。考虑用一个栈存球的大小是$2$的多少次方,每次插入球后,不断取出后面两个球,大小相同则合并,否则插入下一个......
  • XYCTF pwn部分题解 (部分题目详解)
    hello_world(签到)思路:✅这道题就是利用printf函数泄露libc的基地址,然后再次进行栈溢出通过system,/bin/sh来获取shellwp:invisible_flag思路:✅题目提示orw,那我们先看看是否开了沙盒那么是开了沙盒的,试试orw读取flag虽然保护全开但是程序会执行我们写的shellcdoe那么就可......
  • 二叉树笔试题解题思路
    数据结构二叉树笔试题:解题思路:1.判断是否为空树,若为空树,则返回0;2.定义两个指针备份根结点地址,定义两个整型变量a,b并初始化为0,记录左右子树的深度;先对根结点的左子树进行遍历,若根结点的左结点不为NULL,则a++,把根结点的左结点赋值为新的根结点,再进行上述操作,若根结点的左结点......