[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;
}