P3453 [POI2007]DRZ-Trees

    • 29通过
    • 86提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 线段树 POI 2007 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB


  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示


    Byteasar has a cottage. Lately, he has bought $n$ trees and had them planted all in one row. Byteasar does not, however, like the order which the trees have been planted in. It particularly annoys him that tall and short ones have been mixed up, and the composition does not meet his aesthetic criteria.

    Byteasar has invented a disorder coefficient so as to allow the gardener to comprehend his intentions: thelower the value of the coefficient the prettier the row of trees. It is defined in the following way:

    $|h_1-h_2|+|h_2-h_3|+\cdots+|h_{n-1}-h_n|$, where $h_1,h_2,\cdots,h_n$ are the heights of consecutive trees in a row. Replanting is a very toilsome and cumbersome task, therefore Byteasar has ordered the gardener to replanttwo trees at the most (i.e. interchange their positions). The task of the gardener is to choose the pair to replantin a way that makes the disorder coefficient the smallest.

    The gardener is not sure if he has chosen the correct pair of trees and he fears he may lose his job ifhe is mistaken. Help him: for each tree calculate the minimal disorder coefficient that may be attained byswitching places with any other tree.

    TaskWrite a programme which:

    reads the height of the consecutive trees in a row from the standard input, for each tree calculates the minimal disorder coefficient that may be attained should it switch places with some other tree (or should there be no change at all), writes the outcome to the standard output.

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



    The first line of the standard input contains one integer $n$ ($2\le n\le 50\ 000$).

    The other contains $n$ integers $h_i$ ($1\le h_i\le 100\ 000\ 000$)separated by single spaces, denoting the height of the consecutive trees in the row.


    The output should consist of precisely $n$ lines. The $i$'th line should contain a single integer - the smallestdisorder coefficient attainable when considering replanting of the $i$'th tree.


    输入样例#1: 复制
    7 4 5 2 5
    输出样例#1: 复制