#P1099. [POI2007]树Drz

    ID: 102 传统题 2000ms 256MiB 尝试: 283 已通过: 77 难度: 8 上传者: 标签>CF2500提高+/省选-绝对值分段线性化离线查询扫描线添加/删除事件普通线段树离散化二分查找增量维护

[POI2007]树Drz

本场部分分与下发大数据

组别 数据限制 本组分值
1 n≤100n\le100 20
2 100<n≤5000100<n\le5000 30
3 5000<n≤500005000<n\le50000 50

本表为本场训练新增分档,并非原POI官方分档。每组内全部测试通过才获得该组分数,三组独立累加,总分100。

下载大样例(输入与答案)


题目描述

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

输入格式

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

输出格式

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

5
7 4 5 2 5
7
7
8
7
7
5
1 2 3 4 5
4
4
4
4
4