F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 1099. -- [POI2007]树Drz

1099: [POI2007]树Drz

Time Limit: 15 Sec  Memory Limit: 162 MB
Submit: 230  Solved: 97
[Submit][Status][Discuss]

Description

  CDQZ是一个偏远的小学校,FGD在学校里中了一排树。他却不喜欢这些树的顺序,因为他们高高矮矮显得那么
参差不齐。FGD定义这些树的不整齐程度为相邻两树的高度差的和。设树高分别为h1,h2,h3,…,hn。那么不整齐程
度定义为:|h1-h2|+|h2-h3|+……+|hn-1-hn|。不过,重新栽种这些树是一件麻烦的事情,所以FGD最多只想交换
其中两个树的位置。现在请你帮助他,他应该怎么交换使得整个一排树的不整齐程度最小。

Input

  第一行包含一个整数n(2<=n<=50000),接下来第二行包含n个正整数h1,h2,h3,…,hn,分别表示树的高度。(1
<=hi<=100000000)

Output

  应该包含n行,每行一个整数,第i行表示若交换的其中一棵树编号为i,则能获得的最小不整齐程度为多少。

Sample Input

样例输入1
5
7 4 5 2 5

样例输入2
5
1 2 3 4 5

Sample Output

样例输出1
7
7
8
7
7

样例输出2
4
4
4
4
4

HINT

Source

[Submit][Status][Discuss]

HOME Back