网站开发及流行框架,建设图书馆网站,ai的优点和缺点,同ip网站题目
分组【算法赛】
难度: 中等
问题描述
蓝桥小学要进行弹弹球游戏#xff0c;二年级一班总共有 n 个同学#xff0c;要求分成 k 个队伍#xff0c;由于弹弹球游戏要求队员的身高差不能太大#xff0c;小蓝是班长#xff0c;他对这个事情正在发愁#xff0c;他想问…题目
分组【算法赛】
难度: 中等
问题描述
蓝桥小学要进行弹弹球游戏二年级一班总共有 n 个同学要求分成 k 个队伍由于弹弹球游戏要求队员的身高差不能太大小蓝是班长他对这个事情正在发愁他想问你如何最小化每个组之间的身高极差。
具体的假设分成了 k 个组第 i 组最高的人身高是 Hxi 最矮的是 Hni你被要求最小化表达式 max1≤i≤k max(Hxi−Hni) 。直白来说你需要将 n 个元素分出 k 组使得最大的极差尽可能小。你需要输出这个最小化后的值。
输入格式
第一行输入两个整数 n,k 。
第二行输入 n 个整数h1,h2,h3...hn 分别代表 n 个人的身高。
输出格式
输出一个整数代表最小值。
样例输入
5 3
8 4 3 6 9样例输出
1说明
样例分组情况{ 3,43,4 } { 66 } { 8,98,9 } 。
评测数据规模
数据范围 1≤k≤n≤105,1≤hi≤109 。
运行限制
语言最大运行时间最大运行内存C1s256MC1s256MJava2s256MPython33s256MPyPy33s256M 思路和解题方法
(注释楼房等于学生楼高等于身高) #include iostream包含输入输出流库提供与标准输入输出设备的接口。#include vector包含向量库提供向量容器及其操作。#include algorithm包含算法函数库提供各种常用的算法操作。using namespace std;使用std命名空间简化对标准库的调用。bool check(vectorint heights, int k, int max_diff)定义一个函数用于检查是否可以将数组分成不超过k个连续子序列且每个子序列中的最大值和最小值之差不超过max_diff。int main()主函数程序的入口。cin n k;从标准输入读取两个整数分别赋值给变量n和k表示楼房个数和要求的连续子序列数量。vectorint heights(n);声明一个具有n个元素的向量heights用于存储每个楼房的高度。for (int i 0; i n; i) cin heights[i];循环n次从标准输入读取每个楼房的高度并存储到向量heights中。sort(heights.begin(), heights.end());对楼房的高度进行升序排序以便后面的二分查找。int l 0, r heights[n - 1] - heights[0];定义二分查找的左边界l和右边界r初始分别为0和最大高度和最小高度之差。while (l r)当左边界l小于右边界r时执行二分查找。int mid l (r - l) / 2;计算中间值mid这样可以避免整数溢出。if (check(heights, k, mid)) r mid;如果可以将数组分成不超过k个连续子序列且每个子序列中的最大值和最小值之差不超过mid则更新右边界r为mid。else l mid 1;否则更新左边界l为mid1。cout l endl;输出最小的最大差值。return 0;返回0表示程序正常结束。 复杂度 时间复杂度: O(n*log n) 时间复杂度是O(nlogn)其中n是楼房的个数。主要包括排序操作和二分查找操作。 排序操作的时间复杂度为O(nlogn)即对楼房的高度进行升序排序。 二分查找操作的时间复杂度为O(logN)其中N表示最大高度和最小高度之差。每次查找都将搜索空间缩小一半直到找到最小的最大差值。 因此整个算法的时间复杂度为O(nlogn logN)可以近似视为O(nlogn)。 空间复杂度 O(n) 算法的空间复杂度是O(n)用于存储楼房的高度。 c 代码
#include iostream
#include vector
#include algorithmusing namespace std;// 检查是否可以将数组分成不超过k个连续子序列且每个子序列中的最大值和最小值之差不超过max_diff
bool check(vectorint heights, int k, int max_diff) {int cnt 1; // 计数器cnt记录分割出的子序列个数默认为1int cur heights[0]; // 当前子序列的起始值初始为数组第一个元素的高度int n heights.size(); // 数组的长度for (int i 1; i n; i) { // 从第二个元素开始遍历数组if (heights[i] - cur max_diff) { // 如果当前元素和起始值的差大于max_diffcnt; // 分割出一个新的子序列cur heights[i]; // 更新当前子序列的起始值为当前元素的高度}}return cnt k; // 返回是否分割出的子序列个数小于等于k
}int main() {int n, k;cin n k; // 输入n和kvectorint heights(n); // 声明一个具有n个元素的向量heights存储每个楼房的高度for (int i 0; i n; i) {cin heights[i]; // 输入每个楼房的高度并存储到向量heights中}sort(heights.begin(), heights.end()); // 对楼房的高度进行升序排序int l 0; // 定义二分查找的左边界l初始为0int r heights[n - 1] - heights[0]; // 定义二分查找的右边界r初始为最大高度和最小高度之差while (l r) { // 当左边界小于右边界时执行二分查找int mid l (r - l) / 2; // 计算中间值midif (check(heights, k, mid)) { // 如果可以将数组分成不超过k个连续子序列且每个子序列中的最大值和最小值之差不超过midr mid; // 更新右边界为mid} else {l mid 1; // 更新左边界为mid1}}cout l endl; // 输出最小的最大差值return 0;
}觉得有用的话可以点点赞支持一下。
如果愿意的话关注一下。会对你有更多的帮助。 每天都会不定时更新哦 人 。
