贪心算法

数据结构、算法总述：数据结构/算法 C/C++-CSDN博客

---

贪心算法（greedy algorithm）

是一种解决优化问题的算法，其基本思想是在问题的每个决策阶段，都选择当前看起来最优的选择，即贪心地做出局部最优的决策，以期获得全局最优解。

问题特点：

• 贪心选择性质：只有当局部最优选择始终可以导致全局最优解时，贪心算法才能保证得到最优解。
• 最优子结构：原问题的最优解包含子问题的最优解。

解决步骤：

1. 问题分析：梳理与理解问题特性，包括状态定义、优化目标和约束条件等。这一步在回溯和动态规划中都有涉及。
2. 确定贪心策略：确定如何在每一步中做出贪心选择。这个策略能够在每一步减小问题的规模，并最终解决整个问题。
3. 正确性证明：通常需要证明问题具有贪心选择性质和最优子结构。这个步骤可能需要用到数学证明，例如归纳法或反证法等。

区间问题

区间选点

题目
给定 N个闭区间[ ai, bi ]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点 输出选择的点的最小数量。

#include
#include
using namespace std;

const int N = 100010;
int n;

struct Range 
{
    int l, r;
    bool operator ed) 
        {
            res++; // 点的数量加一
            ed = range[i].r;
        }
    }

    printf("%dn", res);
    return 0;
}

最大不相交区间数量

题目
给定N个闭区间[ai,bi]，请你在数轴上选择若干区间，使得选中的区间之间互不相交(包括端点)。
输出可选取区间的最大数量。

#include 
#include 
using namespace std;

const int N = 100010;
int n;

struct Range 
{
    int l, r;
    bool operator ed) 
        {
            res++;
            ed = range[i].r;
        }
    }
    
    printf("%dn", res);
    return 0;
}

区间分组

题目
给定N个闭区间[ai,bi]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。
输出最小组数。

#include 
#include 
#include 
using namespace std;

const int N = 1e5 + 10;
int n;

struct Range 
{
    int l, r;
    bool operator, greater>heap; // 小根堆维护所有组的右端点最小值 
    
    for (int i = 0; i = r.l)
            heap.push(r.r);
        else 
        {
          服务器托管  heap.pop();
            heap.push(r.r);
        }
    }
    
    printf("%dn", heap.size());
    return 0;
}

区间覆盖

题目
给定N个闭区间[ai,bi] 以及一个线段区间[s,t]，请你选择尽量少的区间，将指定线段区间完全覆盖。
输出最少区间数，如果无法完全覆盖则输出−1。

#include 
#include 
using namespace std;

const int N = 100010;

int n;
struct Range
{
    int l, r;
    bool operator= ed)
        {
            success = true;
            br服务器托管eak;
        }

        st = r;
        i = j - 1; 
    }

    if (!success) res = -1;
    printf("%dn", res);

    return 0;
}

排序不等式

排队打水

题目
有n个人排队到11个水龙头处打水，第i个人装满水桶所需的时间是ti，请问如何安排他们的打水顺序才能使所有人的等待时间之和最小？

#include 
#include 
using namespace std;

typedef long long LL;
const int N = 100010;
int n;
int t[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i 

绝对值不等式

货仓选址

题目
在一条数轴上有N家商店，它们的坐标分别为A1∼AN。现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。
为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

#include 
#include 
using namespace std;

const int N = 100010;
int n;
int q[N];

int main()
{
    scanf("%d", &n);

    for (int i = 0; i 

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: ts环境下如何解决第三方npm包类型报错的问题

在 TypeScript 环境下，当引入第三方 npm 包时出现类型报错的问题，可以尝试以下几种解决方法： 1、安装 @types 包：许多流行的第三方 npm 包都有对应的 TypeScript 类型声明文件，这些声明文件通常以 @types/包名 的形式发…