CF1216B Shooting

最近，Vasya 决定提升自己的手枪射击技能。今天他的教练给他布置了如下练习：他在桌子上按顺序摆放了 $n$ 个易拉罐，编号从左到右依次为 $1$ 到 $n$。Vasya 需要将每个易拉罐恰好击倒一次，才能完成练习。他可以自由选择击倒易拉罐的顺序。 Vasya 知道第 $i$ 个易拉罐的耐久度为 $a_i$。这意味着，如果 Vasya 已经击倒了 $x$ 个易拉罐，现在准备开始射击第 $i$ 个易拉罐，他需要用 $(a_i \cdot x + 1)$ 次射击才能将其击倒。你可以假设 Vasya 一旦开始射击某个易拉罐，就会一直射击直到将其击倒。 你的任务是选择一种击倒易拉罐的顺序，使得击倒所有 $n$ 个易拉罐所需的总射击次数最少。

输入的第一行包含一个整数 $n$，表示易拉罐的数量，$2 \le n \le 1000$。 第二行包含 $a_1, a_2, \dots, a_n$，其中 $a_i$ 表示第 $i$ 个易拉罐的耐久度，$1 \le a_i \le 1000$。

第一行输出击倒所有 $n$ 个易拉罐所需的最少射击次数。 第二行输出 $n$ 个互不相同的整数，表示最优的击倒顺序（即易拉罐的编号）。如果有多种最优方案，可以输出任意一种。

在第一个样例中，Vasya 可以先击倒第一个易拉罐。由于之前没有击倒任何易拉罐，他只需射击 $1$ 次即可击倒它。之后，他可以击倒第三个易拉罐，需要射击 $20 \cdot 1 + 1 = 21$ 次。最后只剩下第二个易拉罐，需要射击 $10 \cdot 2 + 1 = 21$ 次。因此总共需要 $1 + 21 + 21 = 43$ 次射击。 在第二个样例中，由于所有易拉罐的耐久度相同，击倒顺序不会影响总射击次数。 由 ChatGPT 4.1 翻译