题面描述

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

思路

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

具体步骤

P3054.根据某条件聚类最少交换次数(100分)

1000ms

Tried: 183

Accepted: 47

Difficulty: 3

所属公司 : 华为od

算法与标签>滑动窗口

题目描述

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

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

数据范围：

$-100 <= K <= 100$

$-100 <=$ 数组中数值 $<= 100$

输入描述

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

第二行输入 $K$ 数值： $2$

输出描述

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

样例1

输入

1 3 1 4 0
2

输出

说明

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

输入

预期输出（选填）

题面描述

思路

具体步骤

P3054.根据某条件聚类最少交换次数(100分)

题目描述

输入描述

输出描述

样例1

Status

Development

Support

About