小红的奶油蛋糕工坊_

$\hspace{15pt}$ 小红新烤制了 $n$ 块奶油蛋糕，每块蛋糕都有一个独特的初始“甜度值”。这 $n$ 块蛋糕的甜度值恰好构成了一个长度为 $n$ 的排列 $a_1, a_2, \dots, a_n$ 。
$\hspace{15pt}$ 为了让蛋糕的口感更加和谐，小红希望调整部分蛋糕的甜度，使得工坊中至少有 $\lceil \tfrac{n}{2} \rceil$ 块蛋糕的甜度值完全相同。调整一块蛋糕的甜度是有代价的：如果将一块甜度为 $u$ 的蛋糕调整为甜度 $v$ ，所需的奶油成本为 $|u - v|$ 。
$\hspace{15pt}$ 作为一名精打细算的店长，小红希望在总成本最小的前提下，完成这个调整目标。请你帮她计算出调整后每块蛋糕的甜度值。

【名词解释】
$\hspace{15pt}$ 长度为 $n$ 的排列：由 $1,2,\dots,n$ 这 $n$ 个整数、按任意顺序组成的数组（每个整数均恰好出现一次）。例如， $\{2,3,1,5,4\}$ 是一个长度为 $5$ 的排列，而 $\{1,2,2\}$ 和 $\{1,3,4\}$ 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。
$\hspace{15pt}$ $\lceil x \rceil$ ：代表对 $x$ 进行上取整操作，得到不小于 $x$ 的最小整数。

$\hspace{15pt}$ 在一行上输出 $n$ 个整数 $p_1, p_2, \dots, p_n \left(-10^9 \leqq p_i \leqq 10^9\right)$ ，表示在最小成本下，调整后每块蛋糕的甜度值。

$\hspace{15pt}$ 如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

说明

在这个样例中，，因此至少需要有  块蛋糕的甜度值相同。其中一种可行的方案是选择初始甜度为  和  的两块蛋糕，并将它们都调整为甜度 ：
初始甜度为  的蛋糕保持不变，成本为 ；
初始甜度为  的蛋糕调整为 ，成本为 。
总成本为 。

小红的奶油蛋糕工坊

输入描述:

输出描述:

输入

输出

说明

输入

输出

问题信息

热门推荐

相关试题