Codeforces Wilbur and Array

Description

Wilbur the pig is tinkering with arrays again. He has the array a1, a2, ..., an initially consisting of n zeros. At one step, he can choose any index i and either add 1 to all elements ai, ai + 1, ... , an or subtract 1 from all elements ai, ai + 1, ..., an. His goal is to end up with the array b1, b2, ..., bn.

Of course, Wilbur wants to achieve this goal in the minimum number of steps and asks you to compute this value.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the length of the array ai. Initially ai = 0 for every positioni, so this array is not given in the input.

The second line of the input contains n integers b1, b2, ..., bn ( - 109 ≤ bi ≤ 109).

Output

Print the minimum number of steps that Wilbur needs to make in order to achieve ai = bi for all i.

Sample Input

Input
5
1 2 3 4 5
Output
5
Input
4
1 2 2 1
Output
3

Hint

In the first sample, Wilbur may successively choose indices 1, 2, 3, 4, and 5, and add 1 to corresponding suffixes.

In the second sample, Wilbur first chooses indices 1 and 2 and adds 1 to corresponding suffixes, then he chooses index 4 and subtract 1.

题意:给你一个数组b[](这个数组输入值)每次可以修改数组a[]中a[i]到a[n]的值(这些数同时加1或者减1  a数组初始化为0)问你最少操作多少次可以使a数组完全等于b数组

题解:因为我们每次只能确定一个数的值(即a[i] i从1到n依次取值)所以我们应当记录下每次确定一个数需要的步数,总步数就是确定所有数的步数之和   将b数组循环遍历一遍,用sum记下操作步数,用s记录当前操作过后a[i+1]的值

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#define LL long long
#define MAX 200100
using namespace std;
int b[MAX];
int main()
{
	int n,i;
	while(scanf("%d",&n)!=EOF)
	{
		for(i=0;i<n;i++)
		    scanf("%d",&b[i]);
		__int64 s=0;
		__int64 sum=0;
		for(i=0;i<n;i++)
		{
			if(s<b[i])
			{
				sum+=(b[i]-s);//s小于b[i]则这个数需要操作b[i]-s步 
				s+=(b[i]-s);//因为上边的操作为a[i]+1   +1操作所以s取值变为 += 
			}
			if(s>b[i])
			{
				sum+=(s-b[i]);//s大于b[i]则这个数需要操作s-b[i]步 
				s-=(s-b[i]);//因为上边的操作为a[i]-1   -1操作所以s取值变为 -=
			}
		}
		printf("%I64d
",sum);
	}
	return 0;
}

  

原文地址:https://www.cnblogs.com/tonghao/p/5114177.html