题解：不完全柯西序列判定

这道题目虽然套用了“数学分析”和“柯西序列”的概念，但其本质是一个简单的数组差分序列性质判定问题。

1. 题目分析

定义提取：

• 距离序列：$d_i = |a_i - a_{i+1}|$。
• 不完全柯西序列的条件：距离序列 $\{d_i\}$ 必须是（不严格）递减的。
• 判定目标：给定一个长度为 $n$ 的数组，判断它是否满足 $\forall i \in [1, n-2]$，都有 $d_i \ge d_{i+1}$。

通俗理解： 就是看这个数组里，相邻两项之间的“跳跃幅度”是不是在不断缩小（或者保持不变）。如果幅度变大了，就不符合条件。

2. 解题步骤

1. 计算差值的绝对值： 遍历数组，计算 $d_i = |a_i - a_{i+1}|$。对于长度为 $n$ 的数组，共有 $n-1$ 个差值。
2. 验证递减性： 检查是否满足 $d_1 \ge d_2 \ge d_3 \ge \dots \ge d_{n-1}$。 只要出现任何一个 $d_i < d_{i+1}$，立即判定为 No。
3. 处理数据范围：

• $n \le 2 \times 10^5$：需要 $O(n)$ 的线性算法，不能用 $O(n^2)$。
• $|a_i| \le 10^9$：差值的绝对值可能达到 $2 \times 10^9$，在 C++ 中建议使用 long long 以防万一，尽管 int 在 32 位环境下通常也够用。

3. 代码实现 (C++)

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

typedef long long ll;

void solve() {
    int n;
    if (!(cin >> n)) return;

    vector<ll> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // 计算并检查相邻项的距离是否递减
    bool possible = true;
    ll last_dist = -1;

    for (int i = 0; i < n - 1; ++i) {
        // 计算当前距离 d_i = |a_i - a_{i+1}|
        ll current_dist = abs(a[i] - a[i + 1]);

        // 如果不是第一个距离，则与上一个距离比较
        if (i > 0) {
            if (current_dist > last_dist) {
                possible = false;
                break;
            }
        }
        last_dist = current_dist;
    }

    if (possible) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

4. 样例推演

样例 2：1 100 50 75 75

1. $d_1 = |1 - 100| = 99$
2. $d_2 = |100 - 50| = 50$ （$99 \ge 50$，OK）
3. $d_3 = |50 - 75| = 25$ （$50 \ge 25$，OK）
4. $d_4 = |75 - 75| = 0$ （$25 \ge 0$，OK）

• 结论：Yes。

样例 3：1 100 300 300 300

1. $d_1 = |1 - 100| = 99$
2. $d_2 = |100 - 300| = 200$ （$99 < 200$，违反递减性）

• 结论：No。

5. 复杂度分析

• 时间复杂度： $O(n)$。只需对数组进行一次遍历，计算 $n-1$ 次差值并做 $n-2$ 次比较。
• 空间复杂度： $O(n)$。用于存储输入数组 $a$。如果边读入边处理，可以将空间复杂度优化到 $O(1)$。