题目解析与代码分析

题目背景

Frank 是一名股票交易员，他使用两个整数 $m$ 和 $n$ ($1 \leq m < n \leq 100$) 作为他的交易策略参数。他每天计算前 $m$ 天和前 $n$ 天的股票价格平均值 $P(m)$ 和 $P(n)$，以此判断股票的趋势（看涨或看跌）。根据趋势的变化，Frank 决定买入或卖出股票。

题目要求

1. 输入：

   • 整数 $m$, $n$, $k$ ($n < k \leq 10,000$)。
   • $k$ 行股票价格，每行格式为 $L[i].R[i]$（小数点后两位）。

2. 输出：

   • 根据趋势变化生成买入或卖出信号：
     • 如果 $P(m) > P(n)$，生成“第 $i$ 天买入”信号。
     • 如果 $P(m) < P(n)$，生成“第 $i$ 天卖出”信号。

解题方法

数据结构设计

1. 数组定义：

   • p[k+1]：存储原始股票价格（整数形式）。
   • L[k+1], R[k+1]：存储股票价格的小数部分。
   • sum[k+1]：存储前缀和，用于快速计算区间和。
   • pm[k+1]：存储前 $m$ 天的平均值。
   • pn[k+1]：存储前 $n$ 天的平均值。

2. 预处理：

   • 将输入的股票价格转换为整数形式存储在 p[] 中，并记录小数部分在 L[] 和 R[] 中。
   • 计算前缀和数组 sum[]，方便快速求解区间和。

3. 计算平均值：

   • 根据公式：$$P(m)_i = \frac{\text{sum}[i] - \text{sum}[i-m]}{m} $$$$P(n)_i = \frac{\text{sum}[i] - \text{sum}[i-n]}{n} $$

4. 判断趋势变化：

   • 初始化第一天（第 $n$ 天）的趋势。
   • 遍历后续天数，比较 $P(m)$ 和 $P(n)$ 的大小，判断是否发生趋势反转：
     • 如果趋势从看跌变为看涨，生成“买入”信号。
     • 如果趋势从看涨变为看跌，生成“卖出”信号。

代码实现

以下是基于上述方法的代码实现：

#include <cstdio>
 
using namespace std;
 
const int maxn = 10000 + 10;
const double eps = 1e-8;
 
int p[maxn], L[maxn], R[maxn];
long long sum[maxn];
double pm[maxn], pn[maxn];
 
int main()
{
    int m, n, k;
    while(scanf("%d%d%d", &m, &n, &k) == 3){
        // 初始化前缀和数组
        sum[0] = 0;
        for(int i = 1; i <= k; i++){
            // 输入股票价格并转换为整数形式
            scanf("%d.%d", &L[i], &R[i]);
            p[i] = L[i] * 100 + R[i];
            sum[i] = sum[i-1] + p[i];
        }
        
        // 计算前 m 天的平均值
        for(int i = m; i <= k; i++) pm[i] = (double)(sum[i] - sum[i-m]) / m;
        
        // 计算前 n 天的平均值
        for(int i = n; i <= k; i++) pn[i] = (double)(sum[i] - sum[i-n]) / n;
        
        // 判断第 n 天的趋势
        if(pm[n] - pn[n] > eps) printf("BUY ON DAY %d\n", n);
        else if(pn[n] - pm[n] > eps) printf("SELL ON DAY %d\n", n);
        
        // 遍历后续天数，判断趋势变化
        for(int i = n+1; i <= k; i++) {
            if(pm[i] - pn[i] > eps && pn[i-1] - pm[i-1] > eps) printf("BUY ON DAY %d\n", i);
            else if(pn[i] - pm[i] > eps && pm[i-1] - pn[i-1] > eps) printf("SELL ON DAY %d\n", i);
        }
    }
    return 0;
}