题目分析

给定一个音符序列 $A_1, A_2, \ldots, A_n$，我们需要将其调整为非递减序列 $B_1, B_2, \ldots, B_n$，使得最大的调整幅度 $\max |A_i - B_i|$ 最小。

换句话说，我们要找到最小的 $x$，使得存在非递减序列 $B$ 满足对所有 $i$ 都有 $|A_i - B_i| \leq x$。

解题思路

通过贪心算法解决：

1. 问题转化：将原序列调整为非递减序列，且最大调整幅度最小
2. 关键观察：最优解中，最大调整幅度等于序列中最大落差的一半
3. 贪心策略：遍历序列，维护当前最大值，记录最大落差

算法核心

对于序列中的每个位置：

• 如果当前值小于之前遇到的最大值，则计算落差
• 更新遇到的最大值
• 最终答案为最大落差的一半（向上取整）

完整代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 5000005
#define int long long
using namespace std;

int n, sa, sb, sc, sd, a[N], mod;

// 生成函数 F(x) = sa*x^3 + sb*x^2 + sc*x + sd
int F(int x) {
    return (sa * x % mod * x % mod * x % mod + 
            sb * x % mod * x % mod + 
            sc * x % mod + 
            sd) % mod;
}

signed main() {
    // 读取输入
    cin >> n >> sa >> sb >> sc >> sd >> a[1] >> mod;
    
    // 生成序列
    for (int i = 2; i <= n; i++) {
        a[i] = (F(a[i - 1]) + F(a[i - 2])) % mod;
    }
    
    // 贪心求解
    int maxn = a[1];  // 当前遇到的最大值
    int ans = 0;      // 最大落差
    
    for (int i = 2; i <= n; i++) {
        // 如果当前值小于之前最大值，更新最大落差
        if (maxn - a[i] > ans) {
            ans = maxn - a[i];
        }
        // 更新当前最大值
        if (a[i] > maxn) {
            maxn = a[i];
        }
    }
    
    // 输出结果（向上取整）
    cout << (ans + 1) / 2 << endl;
    
    return 0;
}

代码说明

主要函数：

• F(x)：计算生成函数的值
• 主函数：生成序列并执行贪心算法

算法步骤：

1. 序列生成：根据递推公式 $A_i = F(A_{i-1}) + F(A_{i-2})$ 生成序列
2. 贪心遍历：
   • 初始化 maxn = a[1]，ans = 0
   • 对于每个位置 $i$：
     • 如果 a[i] < maxn，更新 ans = max(ans, maxn - a[i])
     • 更新 maxn = max(maxn, a[i])
3. 结果计算：输出 (ans + 1) / 2（向上取整）

关键变量：

• maxn：遍历过程中遇到的最大值
• ans：序列中的最大落差

正确性证明

考虑最坏情况：序列中有一个很高的峰值，后面跟着一个很低的谷值。为了使其非递减，我们需要：

• 将峰值降低 $x$
• 将谷值提高 $x$

使得调整后的值相等。因此最大调整幅度为落差的一半。

复杂度分析

• 时间复杂度：$O(n)$
  • 序列生成：$n-1$ 次递推
  • 贪心遍历：$n-1$ 次比较
• 空间复杂度：$O(n)$ 存储序列