ABC 133 D Rain Flows Into Dams

Problem Statement

There are N mountains in a circle, called Mountain 1, Mountain 2, ..., Mountain N in clockwise order. N is an odd number.

Between these mountains, there are N dams, called Dam 1, Dam 2, ..., Dam N. Dam i $(1≤i≤N)$ is located between Mountain i and i+1 (Mountain N+1 is Mountain 1).

When Mountain i $(1≤i≤N)$ receives $2x$ liters of rain, Dam i−1 and Dam i each accumulates $x$ liters of water (Dam 0 is Dam N).

One day, each of the mountains received a non-negative even number of liters of rain.

As a result, Dam i $(1≤i≤N)$ accumulated a total of $A_i$ liters of water.

Find the amount of rain each of the mountains received. We can prove that the solution is unique under the constraints of this problem.

Constraints

All values in input are integers.
$3≤N≤10^5−1$
N is an odd number.
$0≤A_i≤10_9$
The situation represented by input can occur when each of the mountains receives a non-negative even number of liters of rain.

Input

Input is given from Standard Input in the following format:

N
A1 A2 ... AN

Output

Print N integers representing the number of liters of rain Mountain 1, Mountain 2, ..., Mountain N received, in this order.

人工翻译

有N座山顺时针围成一个环,命名为 $mountain_1$ , $mountain_2$ ... $mountain_N$,N是奇数。

在每座山之间有一座大坝,叫做 $dam_1$ , $dam_2$ ... $dam_N$ , $dam_i$ 处于 $mountain_i$ 和 $mountain_{i-1}$ 之间。($mountain_{N+1}$ 就是 $mountain_1$)

当 $mountain_i$ $(1≤i≤N)$ 收到 $2x$ 升的雨, $dam_{i−1}$ 和 $dam_i$ 各累积 $x$ 升水 ( $dam_0$ 就是 $dam_n$ )。

有一天,每座山各收到了一个非负的偶数升的水。

最后, $dam_i$ $(1≤i≤N)$ 积累了 $A_i$ 升的水。

找到每座山个收到了多少雨。我们可以保证答案是唯一的。

解题思路

一道数学题,只是让程序按一定套路解一个n元一次方程。

$设sum=a_1+a_2+a_3+...+a_n即所有雨量的总和$
$设all=a_2+a_4+...+a_{n-1}(由于n为奇数)$
$设jie[i]为第i个大坝中最初的雨量$
$易得all=\frac{jie[2]}{2}+\frac{jie[3]}{2}+\frac{jie[n]}{2}$
$所以jie[1]=\frac{sum}{2}-all$
$因为 \frac{jie[1]}{2}+\frac{jie[2]}{2}=a[1]$
$所以jie[2]=a[1]-jie[1]$
$同理$
$jie[n]=a[n-1]-jie[n-1]$

代码

#include<bits/stdc++.h>
using namespace std;
int n;
int a[100005];
int sum=0;
int jie[100005];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    int all=0;
    for(int i=2;i<=n;i+=2){
        all+=a[i];
    }
//    cout<<"sum:"<<sum<<"all:"<<all<<endl;
    jie[1]=(sum/2-all);
    cout<<jie[1]*2<<" ";
    for(int i=2;i<=n;i++){
        jie[i]=a[i-1]-jie[i-1];
        cout<<jie[i]*2<<" ";
    }
    return 0;
} 
//

本文链接:https://kaispace.com.cn/index.php/archives/433/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者