#P4331. [BalticOI 2004] Sequence 数字序列

    ID: 4993 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2004线段树Special Judge左偏树BalticOI

[BalticOI 2004] Sequence 数字序列

题目描述

给定一个整数序列a1,a2,,ana_1, a_2, ··· , a_n,求出一个递增序列b1<b2<<bnb_1 < b_2 < ··· < b_n,使得序列aia_ibib_i的各项之差的绝对值之和a1b1+a2b2++anbn|a_1 - b_1| + |a_2 - b_2| + ··· + |a_n - b_n|最小。

输入格式

第一行为数字n(1n106)n (1≤n≤10^6),接下来一行共有nn个数字,表示序列ai(0ai2×109)a_i (0≤a_i≤2×10^9)

输出格式

第一行输出最小的绝对值之和。

第二行输出序列bib_i,若有多种方案,只需输出其中一种。

5
2 5 46 12 1

47
2 5 11 12 13

提示

【数据范围】

40%的数据n5000n≤5000

60%的数据n300000n≤300000

100%的数据n1000000,0ai2×109n≤1000000 , 0≤a_i≤2×10^9

题目来源:BalticBaltic OIOI 20042004 DayDay 1,Sequence1, Sequence

感谢@TimeTraveller提供SPJ。