ABC 133 D Rain Flows Into Dams

nodeee 2019年07月07日

### 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.

## 解题思路

$设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;
}
//