题意回顾

有 $n$ 瓶橙汁排成一排，第 $i$ 瓶的品牌为 $a_i$。
可以花费 $1$ 的代价交换相邻两瓶橙汁。
求最小代价，使得最左边 $k$ 瓶橙汁品牌两两不同。

如果无法实现，输出 $-1$。

数据范围：$n, k \leq 500,000$，$1 \leq a_i \leq n$。

---

初步分析

1. 可行性判断

如果整个序列中不同品牌的数量少于 $k$，那么肯定无法使前 $k$ 个品牌两两不同，输出 $-1$。

---

2. 问题转化

交换相邻元素的最小代价实际上就是逆序对相关的概念。
更准确地说，把一个元素从位置 $i$ 移动到位置 $j$（$j < i$）的最小代价是 $i - j$（因为只能相邻交换）。

我们的目标：选择 $k$ 个不同的品牌，让它们占据前 $k$ 个位置，且移动总代价最小。

---

关键观察

1. 问题重述

我们需要从序列中选出 $k$ 个不同品牌的瓶子，让它们占据位置 $1$ 到 $k$，并且移动总距离最小。

每个瓶子 $i$（品牌为 $a_i$）如果被选入前 $k$ 个位置，设它最终在位置 $p$ ($1 \leq p \leq k$)，那么移动代价为：

• 如果 $i \geq p$，代价 = $i - p$（向左移动）
• 如果 $i < p$，这种情况不会发生，因为我们总是用右边的瓶子填补左边空缺

实际上，由于我们只能交换相邻瓶子，把位置 $i$ 的瓶子移动到位置 $p$ 的代价就是 $i - p$（当 $i > p$）。

---

2. 最优策略

对于前 $k$ 个位置中的每个位置 $p$，我们应该选择尽可能靠左的瓶子来占据它，但要满足品牌不同的约束。

更形式化地说：

• 我们要为位置 $1, 2, \dots, k$ 分配 $k$ 个不同品牌的瓶子
• 每个品牌只能出现一次
• 最小化 $\sum_{p=1}^k (i_p - p)$，其中 $i_p$ 是分配给位置 $p$ 的瓶子的原始位置

即最小化 $\sum_{p=1}^k i_p - \frac{k(k+1)}{2}$。

因此，问题转化为：选择 $k$ 个不同品牌的瓶子，它们的原始位置之和最小。

---

贪心算法

算法步骤

1. 检查可行性：统计所有不同品牌数，如果小于 $k$ 则输出 $-1$
2. 记录每个品牌的所有出现位置
3. 贪心选择：对于每个品牌，我们只关心它最左边的出现位置，因为这样能使位置和最小
4. 选择最小的 k 个位置：从所有品牌的最左位置中，选择最小的 $k$ 个
5. 计算答案：$\text{ans} = \sum_{p=1}^k i_p - \frac{k(k+1)}{2}$

---

• 每个品牌只需要出现一次在前 $k$ 个位置中
• 为了最小化总移动代价，我们应选择每个品牌出现位置最靠前的那个
• 然后从这些最前位置中挑选最小的 $k$ 个（因为位置编号越小，移动代价越小）

---

算法实现细节

数据结构

• 用数组 first_occurrence[b] 记录品牌 $b$ 第一次出现的位置
• 如果某个品牌没有出现，设为无穷大
• 收集所有品牌的第一次出现位置，排序，取前 $k$ 小的

---

复杂度

• 统计第一次出现位置：$O(n)$
• 排序：$O(n \log n)$（最多 $n$ 个不同品牌）
• 总复杂度：$O(n \log n)$，可过 $5 \times 10^5$

---

样例验证

样例 1

$n=5, k=3, a=[3,3,3,1,2]$

各品牌第一次出现位置：

• 品牌3：位置1
• 品牌1：位置4
• 品牌2：位置5

最小的3个位置：$[1,4,5]$

总代价 = $(1+4+5) - \frac{3\times 4}{2} = 10 - 6 = 4$ ✓

---

样例 2

$n=3, k=2, a=[1,1,1]$

不同品牌数 = 1 < 2，输出 $-1$ ✓

---

边界情况

1. $k = 1$：代价总是 $0$（第一个瓶子已经在位置1）
2. $k = n$：需要所有品牌都不同，否则输出 $-1$
3. 有品牌在位置 $> n$：不会发生

---

总结

本题的关键转化：

1. 将相邻交换代价转化为位置差
2. 发现问题等价于选择 $k$ 个不同品牌瓶子的最小位置和
3. 每个品牌只需考虑最左出现位置
4. 贪心选择最小的 $k$ 个位置

通过这种转化，将看似复杂的交换问题转化为简单的贪心选择问题，时间复杂度 $O(n \log n)$，可处理 $n \leq 500,000$ 的数据规模。