A2633. Sequence 数字序列
编程题
省选/NOI-
知识点
题目描述
给定一个整数序列 $a_1, a_2, \cdots , a_n$，求出一个递增序列 $b_1 < b_2 < ··· < b_n$，使得序列 $a_i$ 和 $b_i$ 的各项之差的绝对值之和 $|a_1 - b_1| + |a_2 - b_2| + \cdots + |a_n - b_n|$ 最小。
输入格式
第一行为数字 $n (1≤n≤10^6)$，接下来一行共有 $n$ 个数字，表示序列 $a_i (0≤a_i≤2^{31}-1)$。
输出格式
第一行输出最小的绝对值之和。
第二行输出序列 $b_i$，若有多种方案，只需输出其中一种。
第二行输出序列 $b_i$，若有多种方案，只需输出其中一种。
输入输出样例
输入 #1
5 2 5 46 12 1
输出 #1
47 2 5 11 12 13
说明/提示
【数据范围】
- $40\%$ 的数据 $n≤5000$；
- $60\%$ 的数据 $n≤300000$；
- $100\%$ 的数据 $n≤10^6 , 0≤a_i≤2^{31}-1$；
- $40\%$ 的数据 $n≤5000$；
- $60\%$ 的数据 $n≤300000$；
- $100\%$ 的数据 $n≤10^6 , 0≤a_i≤2^{31}-1$；