1000ms

Difficulty: 6

所属公司 : 阿里

时间 :2025年4月12日-阿里淘天(算法岗)

算法与标签>思维

会员或题库专享

请先，开通会员或购买题库阿里系机考题库，可解锁完整内容。

购买阿里系机考题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（阿里系机考题库），可解锁完整内容。

购买题库开通会员

题解

题面描述

我们有 $n$ 块「记忆碎片」，它们按顺序排列，每块对应的记忆发生时间为 $t_i$ ，且 $t_1,t_2,\dots,t_n$ 构成 $1$ 到 $n$ 的一个排列。目标是将这些碎片重新排列成单调递增的顺序，也就是排序为 $1,2,\dots,n$ 。允许的交换操作必须满足：

每次只能交换两块**发生时间相差不超过 $k$ **的碎片；
如果交换的两块碎片的记忆时间差恰好为 $1$ ，则需要消耗 $1$ 点精力（即代价 $1$ ）；
如果交换碎片的记忆时间差大于 $1$ （但不超过 $k$ ），则交换是免费的。

题目内容

你得到了 $n$ 块「记忆碎片」，它们排成一排，第 $i$ 块碎片所对应记忆发生的时间为 $t_i$ ;。t1,t2,...,tn是1到n的一个排列。

你希望重新排列这 $n$ 块碎片，使它们单调递增(即重排为 $1,2,...,n$ ) ，排列的规则为:

你有一个能力值 $k$ ，每次你可以选择两块发生时间相差不超过 $k$ 的碎片，交换它们的顺序;
由于发生时间过于靠近的两块碎片很难回想，对于两块发生时间相差恰好为 $1$ 的碎片，交换它们需要消耗你 $1$ 点精力;