题面描述

给定一个整数 $K$ 和一个整数数组，请输出将所有小于 $K$ 的数字组合到一起所需的最少交换次数。组合到一起的意思是这些数字在数组中连续排列，但不要求它们在原数组中的相对位置不变。

思路

记所有小于$K$的数的数量为count,那么我们用一个长度为current_count(初始为count)的滑动窗口扫描数组，每次移动时相当于窗口第一个数被弹出去，数组下一个数被加进来，那么我们记录max_count表示小于$K$的数最多时是多少，那么最少需要交换的次数就等于count-max_count

具体步骤

1. 读取输入：

   • C++ 和 Java 通过标准输入读取数组和 $K$ 值。
   • Python 使用 sys.stdin 读取输入，确保高效处理。

2. 统计小于 $K$ 的元素数量：

   • 通过遍历数组，统计满足条件的元素数量 count。

3. 滑动窗口初始化：

   • 计算第一个窗口（前 count 个元素）中满足条件的元素数量 current_count。

4. 滑动窗口遍历：

   • 从窗口的下一个元素开始，逐步滑动窗口。
   • 每次滑动时，检查移出窗口的元素和新进入窗口的元素是否满足条件，更新 current_count。
   • 记录滑动过程中 current_count 的最大值 max_count。

5. 计算最少交换次数：

   • 最少交换次数为 count - max_count，因为在最佳窗口中需要交换的元素最少。

6. 输出结果：

   • 输出计算得到的最少交换次数。

cpp

#include <bits/stdc++.h>
using namespace std;

int main(){
    // 读取第一行输入的数组
    string line;
    getline(cin, line);
    vector<int> arr;
    int num;
    stringstream ss(line);
    while(ss >> num){
        arr.push_back(num);
    }

    // 读取第二行输入的K值
    int K;
    cin >> K;

    // 统计小于K的元素数量
    int count = 0;
    for(auto &x: arr){
        if(x < K) count++;
    }

    // 如果没有小于K的元素或全部小于K，交换次数为0
    if(count == 0 || count == arr.size()){
        cout << 0;
        return 0;
    }

    // 初始化滑动窗口
    int current_count = 0;
    for(int i=0;i<count;i++){
        if(arr[i] < K) current_count++;
    }

    int max_count = current_count;

    // 滑动窗口遍历
    for(int i=count;i<arr.size();i++){
        // 移出窗口的元素
        if(arr[i - count] < K) current_count--;
        // 新进入窗口的元素
        if(arr[i] < K) current_count++;
        // 更新最大值
        max_count = max(max_count, current_count);
    }

    // 计算最少交换次数
    int min_swaps = count - max_count;
    cout << min_swaps;
}

python

# 读取第一行输入的数组
import sys

def main():
    import sys
    arr = list(map(int, sys.stdin.readline().strip().split()))
    # 读取第二行输入的K值
    K = int(sys.stdin.readline())

    # 统计小于K的元素数量
    count = sum(1 for x in arr if x < K)

    # 如果没有小于K的元素或全部小于K，交换次数为0
    if count == 0 or count == len(arr):
        print(0)
        return

    # 初始化滑动窗口
    current_count = sum(1 for x in arr[:count] if x < K)
    max_count = current_count

    # 滑动窗口遍历
    for i in range(count, len(arr)):
        if arr[i - count] < K:
            current_count -=1
        if arr[i] < K:
            current_count +=1
        if current_count > max_count:
            max_count = current_count

    # 计算最少交换次数
    min_swaps = count - max_count
    print(min_swaps)

if __name__ == "__main__":
    main()

java

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        // 读取第一行输入的数组
        String line = sc.nextLine();
        String[] parts = line.trim().split("\\s+");
        int[] arr = new int[parts.length];
        for(int i=0;i<parts.length;i++) {
            arr[i] = Integer.parseInt(parts[i]);
        }

        // 读取第二行输入的K值
        int K = sc.nextInt();

        // 统计小于K的元素数量
        int count = 0;
        for(int num : arr){
            if(num < K) count++;
        }

        // 如果没有小于K的元素或全部小于K，交换次数为0
        if(count ==0 || count == arr.length){
            System.out.println(0);
            return;
        }

        // 初始化滑动窗口
        int current_count = 0;
        for(int i=0;i<count;i++){
            if(arr[i] < K) current_count++;
        }

        int max_count = current_count;

        // 滑动窗口遍历
        for(int i=count;i<arr.length;i++){
            // 移出窗口的元素
            if(arr[i - count] < K) current_count--;
            // 新进入窗口的元素
            if(arr[i] < K) current_count++;
            // 更新最大值
            if(current_count > max_count){
                max_count = current_count;
            }
        }

        // 计算最少交换次数
        int min_swaps = count - max_count;
        System.out.println(min_swaps);
    }
}

题目描述

给出数字 $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$ 次。