蓝桥杯 第 1 场算法双周赛 第三题 分组【算法赛】c++ 贪心+双指针

题目

分组【算法赛】

难度: 中等

问题描述

蓝桥小学要进行弹弹球游戏，二年级一班总共有 n 个同学，要求分成 k 个队伍，由于弹弹球游戏要求队员的身高差不能太大，小蓝是班长，他对这个事情正在发愁，他想问你，如何最小化每个组之间的身高极差。

具体的，假设分成了 k 个组，第 i 组最高的人身高是 Hxi​ ，最矮的是 Hni​，你被要求最小化表达式： max⁡1≤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 。

运行限制

思路和解题方法

(注释：楼房等于学生，楼高等于身高)

1. #include ：包含输入输出流库，提供与标准输入输出设备的接口。
2. #include ：包含向量库，提供向量容器及其操作。
3. #include ：包含算法函数库，提供各种常用的算法操作。
4. using namespace std;：使用std命名空间，简化对标准库的调用。
5. bool check(vector& heights, int k, int max_diff)：定义一个函数，用于检查是否可以将数组分成不超过k个连续子序列，且每个子序列中的最大值和最小值之差不超过max_diff。
6. int main()：主函数，程序的入口。
7. cin >> n >> k;：从标准输入读取两个整数，分别赋值给变量n和k，表示楼房个数和要求的连续子序列数量。
8. vector heights(n);：声明一个具有n个元素的向量heights，用于存储每个楼房的高度。
9. for (int i = 0; i < n; ++i) cin >> heights[i];：循环n次，从标准输入读取每个楼房的高度，并存储到向量heights中。
10. sort(heights.begin(), heights.end());：对楼房的高度进行升序排序，以便后面的二分查找。
11. int l = 0, r = heights[n - 1] - heights[0];：定义二分查找的左边界l和右边界r，初始分别为0和最大高度和最小高度之差。
12. while (l < r)：当左边界l小于右边界r时，执行二分查找。
13. int mid = l + (r - l) / 2;：计算中间值mid，这样可以避免整数溢出。
14. if (check(heights, k, mid)) r = mid;：如果可以将数组分成不超过k个连续子序列，且每个子序列中的最大值和最小值之差不超过mid，则更新右边界r为mid。
15. else l = mid + 1;：否则更新左边界l为mid+1。
16. cout << l << endl;：输出最小的最大差值。
17. 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 
#include 
#include 
 
using namespace std;
 
// 检查是否可以将数组分成不超过k个连续子序列，且每个子序列中的最大值和最小值之差不超过max_diff
bool check(vector<int>& heights, int k, int max_diff) {
    int cnt = 1; // 计数器cnt，记录分割出的子序列个数，默认为1
    int cur = heights[0]; // 当前子序列的起始值，初始为数组第一个元素的高度
    int n = heights.size(); // 数组的长度
 
    for (int i = 1; i < n; i++) { // 从第二个元素开始遍历数组
        if (heights[i] - cur > max_diff) { // 如果当前元素和起始值的差大于max_diff
            cnt++; // 分割出一个新的子序列
            cur = heights[i]; // 更新当前子序列的起始值为当前元素的高度
        }
    }
 
    return cnt <= k; // 返回是否分割出的子序列个数小于等于k
}
 
int main() {
    int n, k;
    cin >> n >> k; // 输入n和k
 
    vector<int> heights(n); // 声明一个具有n个元素的向量heights，存储每个楼房的高度
    for (int i = 0; i < n; ++i) {
        cin >> heights[i]; // 输入每个楼房的高度并存储到向量heights中
    }
 
    sort(heights.begin(), heights.end()); // 对楼房的高度进行升序排序
 
    int l = 0; // 定义二分查找的左边界l，初始为0
    int r = heights[n - 1] - heights[0]; // 定义二分查找的右边界r，初始为最大高度和最小高度之差
 
    while (l < r) { // 当左边界小于右边界时，执行二分查找
        int mid = l + (r - l) / 2; // 计算中间值mid
 
        if (check(heights, k, mid)) { // 如果可以将数组分成不超过k个连续子序列，且每个子序列中的最大值和最小值之差不超过mid
            r = mid; // 更新右边界为mid
        } else {
            l = mid + 1; // 更新左边界为mid+1
        }
    }
 
    cout << l << endl; // 输出最小的最大差值
    return 0;
}

觉得有用的话可以点点赞，支持一下。

如果愿意的话关注一下。会对你有更多的帮助。

每天都会不定时更新哦  >人<  。