最少交换次数

题目描述

给出数字K,请输出所有结果小于K的整数组合到一起的最少交换次数。

组合一起是指满足条件的数字相邻，不要求相邻后在数组中的位置。

数据范围：

100 <= K <= 100
100 <= 数组中数值 <= 100

输入描述

第一行输入数组：1 3 1 4 0

第二行输入K数值：2

输出描述

第一行输出最少交换次数：1

示例1

输入：
1 3 1 4 0
2

输出：
1

说明：
小于2的表达式是1 1 0, 共三种可能将所有符合要求数字组合一起，最少交换1次。

题目类型

这道题属于滑动窗口算法类型。它通过使用一个固定大小的窗口来遍历数组，来求解最少计算交换次数。在这道题中，滑动窗口的大小是小于K的数字个数。

解题思路

问题理解：

给定一个数组和一个整数K，我们需要找出所有小于K的元素并将它们移动到数组的相邻位置，要求最少交换次数。我们只关心小于K的元素，而对大于等于K的元素不关心。

题目要求输出最少交换次数，即将所有小于K的元素相邻排列所需的最小交换次数。

思路解析：

先统计数组中小于K的元素个数ltCount。

如果所有元素都小于K或都大于等于K，则不需要交换。

使用滑动窗口方法，窗口大小为ltCount，表示要把所有小于K的元素合并成一个连续区域。

遍历数组，并通过窗口计算其中大于等于K的元素的个数。每次滑动窗口时，记录窗口内大于等于K的元素数。

窗口内的大于等于K的元素数即是需要交换的次数，通过不断调整窗口的左右边界来找到最小的交换次数。

具体步骤：

统计数组中小于K的元素个数ltCount。

如果ltCount为0或等于数组长度，直接输出0。

使用一个右边界从0开始扩展，记录窗口内大于等于K的元素个数cnt。

当窗口大小达到ltCount时，计算当前窗口内大于等于K的元素个数，这个值即为需要交换的次数。

通过滑动窗口的方式，不断更新最小交换次数。

C++

#include <bits/stdc++.h>

using namespace std;

int main() {
    string line;
    getline(cin, line);
    stringstream ss(line);
    int num, K;
    vector<int> nums;
    while (ss >> num) nums.push_back(num);
    cin >> K;

    // 统计小于 K 的元素个数
    int ltCount = count_if(nums.begin(), nums.end(), [K](int num) { return num < K; });

    // 如果所有的元素都小于 K 或者都大于等于 K，则不需要交换
    if (ltCount == 0 || ltCount == nums.size()) {
        cout << 0 << endl;
        return 0;
    }

    int ans = INT_MAX;
    // 使用滑动窗口，窗口大小为 ltCount
    int cnt = 0;
    for (int right = 0; right < nums.size();) {
        if (nums[right++] >= K) cnt++;

        // 当窗口的大小达到 ltCount 时，计算需要交换的次数
        if (right >= ltCount) {
            ans = min(ans, cnt);

            // 左侧元素出窗口
            if (nums[right - ltCount] >= K) cnt--;
        }
    }

    cout << ans << endl;

    return 0;
}