题解：序列元素计算

解题思路

这道题目给出了一个递推关系式，要求我们根据已知条件计算出序列中的特定元素$a_1$。关键在于从给定的递推关系中推导出$a_1$的直接计算公式，避免使用递归或迭代方法导致的高时间复杂度。

分析

1. 递推关系：题目给出的关系式为$a_i = \frac{(a_{i-1} + a_{i+1})}{2} - c_i$
2. 已知条件：已知$a_0$、$a_{n+1}$和所有$c_i$
3. 目标：计算$a_1$的值
4. 关键发现：通过展开多个递推式，可以发现$a_1$与$a_0$、$a_{n+1}$和$c_i$之间存在线性关系

实现步骤

1. 推导公式：通过数学推导，将递推关系转化为可以直接计算$a_1$的公式
2. 计算系数和：计算$c_i$的加权和
3. 应用公式：使用推导出的公式直接计算$a_1$的值
4. 输出结果：按要求格式输出结果

代码注释

#include <iostream>
#include <iomanip>  // 用于控制输出格式
#include <vector>   // 使用vector存储c数组

using namespace std;

// 计算a1的函数
double calculate_a1(int n, double a0, double an1, const vector<double>& c) {
    double sum = 0.0;  // 初始化加权和
    
    // 计算c数组的加权和：sum = Σ (n-i)*c[i]
    for (int i = 0; i < n; ++i) {
        sum += (n - i) * c[i];
    }
    
    // 应用推导出的公式计算a1:
    // a1 = [(n+1)*a0 + a_{n+1} - 2*sum] / (n+2)
    double a1 = (n + 1) * a0 + an1 - 2 * sum;
    a1 /= (n + 2);
    
    return a1;  // 返回计算结果
}

int main() {
    int n;
    cin >> n;  // 读取序列长度n
    
    double a0, an1;
    cin >> a0 >> an1;  // 读取首尾元素a0和a_{n+1}
    
    vector<double> c(n);  // 创建存储c_i的数组
    for (int i = 0; i < n; ++i) {
        cin >> c[i];  // 逐个读取c_i的值
    }
    
    // 调用函数计算a1
    double a1 = calculate_a1(n, a0, an1, c);
    
    // 设置输出格式为保留两位小数
    cout << fixed << setprecision(2);
    // 输出计算结果
    cout << a1 << endl;
    
    return 0;  // 程序正常结束
}

复杂度分析

1. 时间复杂度：$O(n)$
   • 需要遍历$c$数组一次计算加权和
   • 其余操作都是常数时间
2. 空间复杂度：$O(n)$
   • 需要存储$c$数组
   • 其他变量使用常数空间