【算法设计】贪心算法设计——均分纸牌、线段覆盖问题(C++实现)

创作不易，本篇文章如果帮助到了你，还请点赞 关注支持一下♡>𖥦<)!!
主页专栏有更多知识，如有疑问欢迎大家指正讨论，共同进步！
更多算法分析与设计知识专栏：算法分析🔥
给大家跳段街舞感谢支持！ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ

一、均分纸牌问题

问题描述

有N堆纸牌，编号分别为1，2，…，n。每堆上有若干张，但纸牌总数必为n的倍数。可以在任一堆上取若干张纸牌，然后移动

移牌的规则为：

• 在编号为1上取的纸牌，只能移到编号为2的堆上；
• 在编号为n的堆上取的纸牌，只能移到编号为n-1的堆上；
• 其他堆上取的纸牌，可以移到相邻左边或右边的堆上。

现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。

算法思想和解题思路

首先计算每堆牌的期望值，也就是每堆牌的总牌数与牌堆数的比值，也即为平均值，然后对每一堆牌的数量与平均值比较，如果当前堆的牌数少于平均值，就需要从下一堆牌中取出差值来补齐当前堆，有的时候会出现前面一堆中的牌数多于后面的一堆中的牌数，这个时候要用到的解法和前面的补给的办法恰好相反，只是将多余的补充出去到下一堆即可。

C++代码

#include <iostream>
using namespace std;
void minStep(int n,int *arr)
{
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum += arr[i];
    }
    int avg = sum / n;
    for (int i = 0; i < n-1; i++)
    {
        if (arr[i] < avg)
        {
            cout<<i+2<<"---->"<<i+1<<":"<< avg - arr[i] << "张" << endl;
            arr[i + 1] = arr[i + 1] - (avg - arr[i]);
            arr[i] = arr[i]+ (avg - arr[i]);
        }

    }
    for (int i = 0; i < n - 1; i++)
    {
        if (arr[i] > avg)
        {
            cout << i+1  << "---->" << i + 2 << ":" << arr[i] - avg << "张" << endl;
            arr[i] = arr[i] - (arr[i] - avg);
            arr[i+1] = arr[i] + (arr[i] - avg);
        }
    }
}
int main()
{
    int n;
    cout << "输入一共几堆纸牌：";
    cin >> n;
    cout << "请分别输入" << n << "堆纸牌的个数：";
    int* a = new int[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    minStep(n,a);
    delete[] a;
    return 0;
}

二、线段覆盖问题

问题描述

在一维空间中存在N条线段，每条线段的起始坐标与终止坐标已知，要求求出这些线段一共覆盖了多大的长度。

算法思想和解题思路

将所有的线段按照其起点坐标进行排序。如果起点的坐标相同，那么按照终点的坐标进行排序。

这样做的目的是为了保证线段在处理过程中始终按照从左到右的顺序排列

初始化一个变量Max，用来存储当前已经覆盖的线段的长度。然后，遍历排序后的线段列表

对于每一个线段，我们检查它的终点是否在当前已经覆盖的线段的最右边

• 如果是，那么我们只需要将当前线段的长度加到Max上。

• 如果不是，我们需要找到当前线段和已覆盖线段之间的所有线段，并将它们的长度累加到Max上。Max就是所有线段覆盖的总长度。

C++代码

#include <iostream>  
using namespace std;

void maxLine(int a[],int b[])
{
    // 初始化最大长度为两个数组的第一个元素之差，作为初始值  
    int Max = b[0] - a[0];

    // 循环遍历两个数组，i从1开始是因为我们只需要考虑非空线段  
    for (int i = 1, j = 0; i < 10; i++)
    {
        // 如果当前a[i] >= b[i]，表示线段a[i]被线段b[i]覆盖  
        if (a[i] >= b[i])
        {
            // 更新最大长度为当前线段的长度加上之前被覆盖的最大长度  
            Max += (b[i] - a[i]);
            // 更新j为当前线段的索引，以便记录被覆盖的线段信息  
            j = i;
        }
        // 如果当前a[i] < b[i]，表示线段a[i]无法被线段b[i]覆盖  
        else
        {
            // 如果b[i] <= b[j]，表示当前线段b[i]也无法覆盖之前的线段b[j]，因此跳过当前循环继续下一次循环  
            if (b[i] <= b[j]) continue;
            // 如果b[i] > b[j]，表示当前线段b[i]可以覆盖之前的线段b[j]，因此更新最大长度和j的值  
            else
            {
                Max += b[i] - b[j];
                j = i;
            }
        }
    }
    cout << "这些线段覆盖的最大长度为" << Max << endl;
}
int main() 
{
    int a[] = { 2,3,4,5,6,7,8,9,10,11 };   // 第一个数组，代表线段的起点  
    int b[] = { 3,5,7,6,9,8,12,10,13,15 }; // 第二个数组，代表线段的终点  
    maxLine(a, b);
    return 0;
}