数据结构、算法总述：数据结构/算法 C/C++-CSDN博客
一个贪心算法总是做出当前最好的选择，也就是说，它期望通过局部最优选择从而得到全局最优的解决方案。 ---《算法导论》
贪心算法（greedy algorithm）
是一种解决优化问题的算法，其基本思想是在问题的每个决策阶段，都选择当前看起来最优的选择，即贪心地做出局部最优的决策，以期获得全局最优解。
问题特点：
- 贪心选择性质：只有当局部最优选择始终可以导致全局最优解时，贪心算法才能保证得到最优解。
- 最优子结构：原问题的最优解包含子问题的最优解。
解决步骤：
- 问题分析：梳理与理解问题特性，包括状态定义、优化目标和约束条件等。这一步在回溯和动态规划中都有涉及。
- 确定贪心策略：确定如何在每一步中做出贪心选择。这个策略能够在每一步减小问题的规模，并最终解决整个问题。
- 正确性证明：通常需要证明问题具有贪心选择性质和最优子结构。这个步骤可能需要用到数学证明，例如归纳法或反证法等。
区间问题
区间选点
题目
给定 N个闭区间[ ai, bi ]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点 输出选择的点的最小数量。
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int n;
struct Range
{
int l, r;
bool operator<(const Range& W) const { return r < W.r; } // 重载小于号
} range[N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
int l, r;
scanf("%d%d", &l, &r);
range[i] = {l, r}; // 读入l,r
}
sort(range, range + n); // 按右端点进行排序
int res = 0, ed = -2e9; // ed代表上一个点的右端点
for (int i = 0; i < n; i++)
{
if (range[i].l > ed)
{
res++; // 点的数量加一
ed = range[i].r;
}
}
printf("%d\n", res);
return 0;
}最大不相交区间数量
题目
给定 N 个闭区间 [ai,bi]，请你在数轴上选择若干区间，使得选中的区间之间互不相交(包括端点)。
输出可选取区间的最大数量。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
struct Range
{
int l, r;
bool operator<(const Range& W) const { return r < W.r; }
} range[N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
int l, r;
scanf("%d%d", &l, &r);
range[i] = {l, r};
}
sort(range, range + n);
int res = 0, ed = -2e9;
for (int i = 0; i < n; i++)
{
if (range[i].l > ed)
{
res++;
ed = range[i].r;
}
}
printf("%d\n", res);
return 0;
}
区间分组
题目
给定 N 个闭区间 [ai,bi]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。
输出最小组数。
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
struct Range
{
int l, r;
bool operator<(const Range& W) const { return l < W.l; } // 按左端点排序
} range[N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
int l, r;
scanf("%d%d", &l, &r);
range[i] = {l, r};
}
sort(range, range + n); // sort排序
priority_queue<int, vector<int>, greater<int>>heap; // 小根堆维护所有组的右端点最小值
for (int i = 0; i < n; i++) // 从左往右枚举
{
auto r = range[i]; // 选择当前区间
if (heap.empty() || heap.top() >= r.l)
heap.push(r.r);
else
{
heap.pop();
heap.push(r.r);
}
}
printf("%d\n", heap.size());
return 0;
}区间覆盖
题目
给定 N 个闭区间 [ai,bi] 以及一个线段区间 [s,t]，请你选择尽量少的区间，将指定线段区间完全覆盖。
输出最少区间数，如果无法完全覆盖则输出 −1。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
struct Range
{
int l, r;
bool operator< (const Range &W)const
{
return l < W.l;
}
}range[N];
int main()
{
int st, ed;
scanf("%d%d", &st, &ed);
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
{
int l, r;
scanf("%d%d", &l, &r);
range[i] = {l, r};
}
sort(range, range + n);
int res = 0;
bool success = false;
for (int i = 0; i < n; i ++ )
{
int j = i, r = -2e9;
while (j < n && range[j].l <= st)
{
r = max(r, range[j].r);
j ++ ;
}
if (r < st)
{
res = -1;
break;
}
res ++ ;
if (r >= ed)
{
success = true;
break;
}
st = r;
i = j - 1;
}
if (!success) res = -1;
printf("%d\n", res);
return 0;
}排序不等式
排队打水
题目
有 n 个人排队到 11 个水龙头处打水，第 i 个人装满水桶所需的时间是 ti，请问如何安排他们的打水顺序才能使所有人的等待时间之和最小？
#include <iostream>
#include <algorithm>
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; i ++ ) scanf("%d", &t[i]);
sort(t, t + n);
reverse(t, t + n);
LL res = 0;
for (int i = 0; i < n; i ++ ) res += t[i] * i;
printf("%lld\n", res);
return 0;
}绝对值不等式
货仓选址
题目
在一条数轴上有 N 家商店，它们的坐标分别为 A1∼AN。现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。
为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int q[N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
sort(q, q + n);
int res = 0;
for (int i = 0; i < n; i ++ ) res += abs(q[i] - q[n / 2]);
printf("%d\n", res);
return 0;
}
