[12月考试] E

[12月考试] E

题目描述

给定 $n$ 个正整数 $a_1,a_2,\dots ,a_n$，小 E 可以进行若干次交换，每一次可以交换两个相邻的整数。

求小 E 至少要交换多少次，才可以让 $a_1$ 是 $n$ 个数里的最小值，$a_n$ 是 $n$ 个数里的最大值，最小值和最大值可能不止一个。

对于所有数据，$2\le n\le 10^5$，$1\le a_i\le 10^9$。

输入格式

输入共 $2$ 行。

第 $1$ 行输入 $1$ 个正整数 $n$。

第 $2$ 行输入 $n$ 个正整数 $a_1,a_2,\dots ,a_n$。

输出格式

输出共 $1$ 行 $1$ 个整数，表示最小的交换次数。

样例 #1

样例输入 #1

5
1 2 3 4 5

样例输出 #1

0

样例 #2

样例输入 #2

7
4 4 4 3 2 2 2

样例输出 #2

7

提示

数据范围

对于 $50\%$ 的数据，$n,a_i\le 6$。

对于额外 $20\%$ 的数据，$a_i\le 2$。

对于所有数据，$2\le n\le 10^5$，$1\le a_i\le 10^9$。

🧠题目核心

• 目标是让第一个元素是最小值之一，最后一个元素是最大值之一。
• 可以交换相邻元素，每交换一次算1次。
• 求最小交换次数。

---

✅问题点分析

• 把最小值元素移动到第一个位置，交换次数 = 该元素的当前索引（因为每次交换往前移动1位）。
• 把最大值元素移动到最后一个位置，交换次数 = (末尾位置索引 - 该元素当前索引)。

---

✅重要细节

• 最小值选最左侧的最小值，因为想往前移，最左侧的最小值移动次数最少。
• 最大值选最右侧的最大值，因为想往后移，最右侧的最大值移动次数最少。

✅特殊情况

• 如果最大值的原始索引小于最小值的原始索引，则两者移动时不会发生冲突，交换次数直接相加即可。
• 如果最大值的索引大于最小值索引，则在移动过程中，两者可能会“穿插”，相当于少交换一次，所以总次数要减1。

🚀 C++实现

#include <iostream>
using namespace std;int main() {int n;cin >> n;int a[100000];int minVal = 1000000001;int maxVal = -1;int minPos = -1; // 最左侧最小值位置int maxPos = -1; // 最右侧最大值位置for (int i = 0; i < n; ++i) {cin >> a[i];if (a[i] < minVal) {minVal = a[i];minPos = i;}if (a[i] >= maxVal) {maxVal = a[i];maxPos = i;}}int ans = minPos + (n - 1 - maxPos);if (minPos > maxPos) ans--;cout << ans << "\n";return 0;
}