← 返回题目列表

Codeforces · 2107/F1

F1. 骑自行车(简易版)

中文机器翻译题面 查看原题

这是问题的简单版本。版本之间的区别在于,在这个版本中,$$$1\le n\le 5\cdot 10^3$$$ 并且不需要输出每个前缀的答案。只有解决了该问题的所有版本,您才能破解。

Leo在市中心做程序员,他的爱人在郊区的一所高中教书。每个周末,Leo都会骑着自行车去郊区,和爱人一起度过一个美好的周末。

现在这条路上有 $$$n$$$ 骑自行车的人在 Leo 前面骑行。它们从前到后编号为 $$$1$$$、$$$2$$$、$$$\ldots$$$、$$$n$$$。最初,Leo 位于第 $$$n$$$ 位自行车手的后面。第 $$$i$$$ 位自行车手的敏捷度值为 $$$a_i$$$。

Leo 想领先于 $$$1$$$-st 骑自行车的人。 Leo 可以根据需要多次执行以下操作:

  • 假设Leo前面的第一个人是骑自行车的人$$$i$$$,他可以走到骑自行车的人$$$i$$$前面,成本为$$$a_i$$$。这使他落后于自行车手 $$$i - 1$$$。
  • 使用他的超能力,交换 $$$a_i$$$ 和 $$$a_j$$$ ($$$1\le i \lt j\le n$$$),成本为 $$$(j - i)$$$。

Leo 想知道排在 $$$1$$$-st 骑车人前面的最低成本。这里你只需要打印整个数组的答案,即$$$[a_1, a_2, \ldots, a_n]$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个正整数$$$n$$$ ($$$1 \leq n \leq 5\cdot 10^3$$$),代表骑自行车的人数。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$5\cdot 10^3$$$。

输出

对于每个测试用例,打印一个整数,表示 Leo 从第 $$$n$$$ 位骑车人后面走到第 $$$1$$$ 位骑车人前面的最小成本。

示例

输入
复制

4
3
1 2 4
4
1 1 1 1
2
1 2
4
4 1 3 2

输出
复制

7
4
3
8

注意

在第一个测试用例中,从第 $$$n$$$ 位骑车人后面的位置移动到第 $$$1$$$ 位骑车人前面的位置的一种可能方法是:

  • Leo 交换 $$$a_2$$$ $$$(i=2)$$$ 和 $$$a_3$$$ $$$(j=3)$$$,则数组变为 $$$[1,4,2]$$$;它的成本为$$$j-i=3-2=1$$$。
  • Leo 位于第 $$$3$$$-rd 骑车人后面,并移动到第 $$$2$$$-nd 骑车人后面;花费$$$a_3=2$$$。
  • Leo 交换 $$$a_1$$$ $$$(i=1)$$$ 和 $$$a_2$$$ $$$(j=2)$$$,则数组变为 $$$[4,1,2]$$$;它的成本为$$$j-i=2-1=1$$$。
  • Leo 位于第 $$$2$$$-nd 骑车人后面,并移动到第 $$$1$$$-st 骑车人后面;成本为$$$a_2=1$$$。
  • Leo 交换 $$$a_1$$$ $$$(i=1)$$$ 和 $$$a_2$$$ $$$(j=2)$$$,则数组变为 $$$[1,4,2]$$$;它的成本为$$$j-i=2-1=1$$$。
  • Leo 领先于 $$$1$$$-st 自行车手;成本为$$$a_1=1$$$。

因此总成本为$$$1+2+1+1+1+1=7$$$。可以证明$$$7$$$是最小成本。

在第二个测试用例中,为了从第 $$$n$$$ 位自行车手后面的位置移动到第 $$$1$$$ 位自行车手的前面,Leo 不应交换任何人的敏捷性值。总成本为$$$1+1+1+1=4$$$。