C++ 代码优化：最小操作次数将数组排序 - 解题思路与示例

C++ 代码优化：最小操作次数将数组排序 - 解题思路与示例

本篇文章将提供一段 C++ 代码，用于计算将一个数组排序所需的最小操作次数。该代码基于以下规则：

1. 数组包含从 1 到 n 的所有整数，每个整数出现一次。
2. 允许的操作是将数组中相邻的两个元素交换位置。
3. 操作步长 k 表示每次交换操作最多可以移动元素 k 个位置。

代码示例：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    int minOps = 0;
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) {
            int j = i + 1;
            while (nums[j] != i + 1) {
                j++;
            }
            if (j - i > k) {
                minOps = -1;
                break;
            }
            for (int l = j; l > i; l--) {
                swap(nums[l], nums[l - 1]);
                minOps++;
            }
        }
    }

    cout << minOps << endl;

    return 0;
}

代码说明：

1. 代码首先读取输入数据 n，k 和数组 nums。
2. 循环遍历数组 nums，对于每个元素 nums[i]，如果它不等于 i+1，则进行以下操作：
   • 查找 nums[i] 所在的正确位置 j。
   • 如果 j-i 大于 k，则表示无法在 k 步内将 nums[i] 移动到正确位置，返回 -1。
   • 否则，将 nums[i] 逐步移动到正确位置，每次移动一个位置，并记录操作次数。
3. 最后输出操作次数 minOps。

输入输出数据示例：

1. 输入数据：

5 2
3 1 4 2 5

2. 输出数据：

2

3. 输入数据：

6 3
1 2 3 4 5 6

4. 输出数据：

0

5. 输入数据：

4 1
4 3 2 1

6. 输出数据：

-1

7. 输入数据：

8 4
5 3 7 1 6 2 8 4

8. 输出数据：

6

9. 输入数据：

3 2
2 3 1

10. 输出数据：

1

总结：

本文提供了一个 C++ 代码示例，用于计算将一个数组排序所需的最小操作次数。代码逻辑清晰易懂，并通过十组输入输出数据示例帮助读者更好地理解代码功能。希望本文能够对您有所帮助。