网站设计与建设第一章,磁力搜索引擎torrentkitty,免费做宣传的网站是,国家企业信用信息官网目录
题目部分
解读与思路
代码实现 题目部分
题目根据某条件聚类最少交换次数题目说明给出数字K#xff0c;请输出所有结果小于K的整数组合到一起的最少交换次数。 组合一起是指满足条件的数字相邻#xff0c;不要求相邻后在数组中的位置。 数据范围 -100 K 10…目录
题目部分
解读与思路
代码实现 题目部分
题目根据某条件聚类最少交换次数题目说明给出数字K请输出所有结果小于K的整数组合到一起的最少交换次数。 组合一起是指满足条件的数字相邻不要求相邻后在数组中的位置。 数据范围 -100 K 100 -100 数组中数值 100输入描述第一行输入数组1 3 1 4 0 第二行输入K数值2输出描述第一行输出最少较好次数1补充说明小于2的表达式是 1 1 0共三种可能将所有符合要求数字组合在一起最少交换1次。-----------------------------------------示例示例1输入1 3 1 4 0 2输出1说明无示例2输入0 0 0 1 0 2输出0说明无示例3输入2 3 2 1输出0说明无 解读与思路
题目解读
第一行输入整形数字 K第二行输入一串整形数字假设这一串整形数字存放在一个数组中。
题目要求从第二行整形数字中找出所有小于 K 的数字。然后通过交换位置的方式使找出的这些数字聚合在一块。
聚合在一块的意思是这些数字两两相邻中间不存在不符合条件大于或等于K的数字。交换位置的规则是数组根据之前的假设数字存放在数组中中的任意两个下标的数字交换都可以交换位置。
在示例 1 中下标为0的数字 1和下标为3的数字4交换后数字串变成了 4 3 1 1 0。此时从第2个元素到第4个元素这3个数字全都小于2K等于2。再次过程中交换了1次。
特别注意在示例 3 中没有数字小于K即不存在满足条件的数字时返回 0。
一个好的题目题干应该准确描述背景、条件和要求。晦涩难懂或有歧义的题目容易产生误导。示例作用是进一步印证题干的描述而不应用于补充题目说明。 出题人在描述问题时部分隐含条件没有描述出来当找不到满足条件的交换次数时返回值应该是多少而且表述不够清晰应明示交换规则为任意两个位置的数字可以相互交换需要结合示例才能准确理解题目意思。
分析与思路
第一行输入的数字设为 k。 第二行输入的一串数字把它存到一个整形数组 arr[] 中。
先遍历数组 arr统计 arr 中小于 k 的数字个数 count并记录这些数字的最小下标 minIdx 和 最大下标 maxIdx。如果 count 为 0则直接返回 0。
题目要求小于 k 的数字聚合在一起那么最终聚合的块的数字是连续的假设聚合块中数字的最小下标为 iMin最大小标为 iMax那么 iMax - iMin count - 1且下标在iMin与iMax之间的所有数字都小于 k 。
对于原始数组如果某个小于 k 的数字其在 arr 中的下标处于闭区间 [iMin, iMax] 中那么它不需要交换如果在其之外需要和其他下标在 [ iMin, iMax ] 中且大于 k 的数字交换。显而易见交换次数为 [iMin, iMax] 这个闭区间闭区间为arr数组的下标中大于 k 的数字的个数。
由于iMin minIdxiMax maxIdx此题的要求可以转换成从 [minIdx, maxIdx] 这个闭区间中找出一个长度为 count 的闭区间闭区间为arr数组的下标使 arr 数组中大于 k 的数字的个数最小。计算出的最小个数即为最终的输出。
在此解法中需要遍历数组两次第二次只需要遍历 [ minIdx, maxIdx - count ]其时间复杂度为 o(n)。由于使用了辅助数组用于存储数字空间复杂度为 o(n)。 代码实现
Java代码
import java.util.Scanner;/*** 根据某条件聚类最少交换次数* since 2023.09.05* version 0.1* author Frank**/
public class TogetherChgCnt {public static void main(String[] args) {Scanner sc new Scanner(System.in);// 第一行输入一串数字以空格分隔String stream sc.nextLine();String[] strArr stream.split( );int[] arr new int[ strArr.length ];for( int i 0; i strArr.length; i ){arr[i] Integer.parseInt( strArr[i] );}// 第二行, kString strK sc.nextLine();int k Integer.parseInt( strK );int minIdx -1;int maxIdx -1;int count 0;for( int i 0; i arr.length; i ){if( arr[i] k ){continue;}count ;if( minIdx -1 ) {minIdx i;maxIdx i;}else{maxIdx i;}}if( count 0 ){System.out.println(0);return;}int curCnt 0;for( int i 0; i count; i ){if( arr[ minIdx i ] k ){curCnt ;}}int rangeCnt curCnt;int stepSize maxIdx - minIdx - count 1;// 在区间[ minIdx, maxIdx ]范围内// 逐个向右移动计算移动后的闭区间中大于 k 的个数 curCnt。for( int i 0; i stepSize; i ){if( arr[ minIdx i ] k ){curCnt --;}if( arr[ minIdx count i ] k){curCnt ;}if( curCnt rangeCnt ){rangeCnt curCnt;} }System.out.println( rangeCnt ); }
}
JavaScript代码
const rl require(readline).createInterface({ input: process.stdin });
var iter rl[Symbol.asyncIterator]();
const readline async () (await iter.next()).value;
void async function() {let input [];while (line await readline()) {input.push(line);}// 第一行数据转换成数组var arr input[0].split( );for (var i 0; i arr.length; i) {arr[i] parseInt(arr[i]);}// 第二行数据,kvar k parseInt(input[1]);var minIdx -1;var maxIdx -1;var count 0;for (var i 0; i arr.length; i) {if (arr[i] k) {continue;}count;if (minIdx -1) {minIdx i;maxIdx i;} else {maxIdx i;}}if (count 0) {console.log( 0 );return;}var curCnt 0;for (var i 0; i count; i) {if (arr[minIdx i] k) {curCnt;}}var rangeCnt curCnt;var stepSize maxIdx - minIdx - count 1;for (var i 0; i stepSize; i) {if (arr[minIdx i] k) {curCnt--;}if (arr[minIdx count i] k) {curCnt;}if (curCnt rangeCnt) {rangeCnt curCnt;}}console.log(rangeCnt);
}();
(完)
