降水 - 题解 - Sanhai's Blogs

题意理解

有 N 座山围成一圈（N 是奇数），每座山 i 会下 $p_i$ 升雨。这些雨水会平均分给左右两个大坝：左边的大坝 i-1 和右边的大坝 i 各得到 $p_i/2$ 升。大坝 i 收集到的总水量就是 $a_i$ 。

所以 $a_i$ 和 $p_i$ 的关系就是：

a_i = \frac{p_i + p_{i+1}}{2}

两边乘 2：

p_i + p_{i+1} = 2a_i \tag{1}

核心思路

这个式子很关键！它告诉我们：只要知道 $p_i$ ，就能算出 $p_{i+1}$ ：

p_{i+1} = 2a_i - p_i \tag{2}

问题就变成了：怎么求出 $p_1$ ？

因为 N 是奇数，我们可以绕一圈用 $p_1$ 把自己表示出来。从 $p_1$ 开始，反复用公式 (2) 推下去：

\begin{aligned} p_2 &= 2a_1 - p_1 \\\ p_3 &= 2a_2 - p_2 = 2a_2 - (2a_1 - p_1) = -2a_1 + 2a_2 + p_1 \\\ p_4 &= 2a_3 - p_3 = 2a_3 - (-2a_1 + 2a_2 + p_1) = 2a_1 - 2a_2 + 2a_3 - p_1 \end{aligned}

我们注意到一个规律：奇数项是 $p_1$ 加上一堆 $\pm 2a_i$ ，偶数项是 $-p_1$ 加上一堆 $\pm 2a_i$ 。

因为 N 是奇数，所以 $p_N$ 也是奇数项，可以写成：

p_N = p_1 + 2(a_1 - a_2 + a_3 - a_4 + \dots - a_{N-1})

注意最后一个方程 (1) 当 $i=N$ 时是：

p_N + p_1 = 2a_N

把 $p_N$ 的表达式代入：

(p_1 + 2(a_1 - a_2 + \dots - a_{N-1})) + p_1 = 2a_N

两边除以 2，得到：

p_1 = a_N - a_1 + a_2 - a_3 + \dots + a_{N-1}

也就是：

p_1 = a_N + \sum_{i=1}^{N-1} (-1)^{i+1} a_i

算法流程

用公式算出 $p_1$
从 $i=1$ 到 $N-1$ ，用递推式 $p_{i+1} = 2a_i - p_i$ 算出所有 $p_i$

复杂度是 $O(N)$ 时间， $O(N)$ 空间（存 $a_i$ 和 $p_i$ 数组）。

代码实现

#include <bits/stdc++.h>
using namespace std;

long long a[100005];
long long p[100005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;

    for (int i = 0; i < N; ++i) cin >> a[i];
    
    // 计算 p1：交错和
    long long p1 = a[N];  // 先放 a_N
    int sign = +1;            // a_1 的系数是 +1
    
    for (int i = 0; i < N - 1; ++i) {
        p1 += sign * a[i];
        sign = -sign;         // 正负交替
    }
    
    p[0] = p1;
    for (int i = 1; i < N; ++i) {
        p[i] = 2LL * a[i - 1] - p[i - 1];
    }
    
    for (int i = 0; i < N; ++i) {
        if (i) cout << ' ';
        cout << p[i];
    }
    cout << '\n';
    return 0;
}

一些小细节

数据范围最大到 $10^9$ ，N 最大到 $10^5-1$ ，所以 $p_i$ 可能很大，要用 long long
N 是奇数这个条件非常关键，如果 N 是偶数，方程组可能无解或有无穷多解