历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing《算法基础课》第6章贪心

作者：

姜萍Jumping , 2020-10-06 22:55:52 , 所有人可见 , 阅读 2490

7

31

AcWing《算法基础课》第6章贪心

区间

区间选点

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

思路

将每个区间按照右端点从小到大进行排序
ed值初始化为无穷小，从前往后枚举区间
如果遍历到的区间的左端点大于记忆区间的右端点（放有点），则把记忆区间更新成当前遍历的区间(只更新右端点，因为只在右端点放点)

证明

假设 $ans$ 是最优解， $cnt$ 是可行解，显然有 $ans \le cnt$
由于算法最后得出 $cnt$ 个两两不相交的区间，覆盖每个区间至少需要 $cnt$ 个点，因此 $ans \ge cnt$
综上所述 $ans = cnt$

核心代码

struct Range
{
    int l, r;
    bool operator< (const Range &W)const
    {
        return r < W.r;
    }
}range[N];

sort(range, range + n);

int res = 0, ed = -2e9;
for (int i = 0; i < n; i ++ )
    if (range[i].l > ed)
    {
        ed = range[i].r;        // 在当前区间的右端点放一个点
        res ++ ;
    }

printf("%d\n", res);

最大不相交区间数量

可以参考区间选点那题，二者在算法思路上是一致的

将每个区间按照右端点从小到大进行排序
ed表示当前放置在数轴上的点的位置，开始初始化为无穷小，表示没有放置，此时数轴上没有点
依次遍历排序好的区间。如果区间的左端点大于当前放置点的位置，说明当前点无法覆盖区间，则把点的位置更新成该区间的右端点，表示在该区间的右端点放置一个新的点，同时更新点的个数

证明

假设 $ans$ 是最优解，表示最多有 $ans$ 个不相交的区间； $cnt$ 是可行解，表示算法求出个不相 $cnt$ 交的区间，显然有 $ans \ge cnt$
反证法证明 $ans \le cnt$ 。假设 $ans \gt cnt$ ，由最优解的含义知，最多有 $ans$ 个不相交的区间，因此至少需要 $ans$ 个点才能覆盖所有区间，而根据算法知，只需 $cnt$ 个点就能覆盖全部区间，且 $cnt < ans$ ，这与前边分析至少需要 $ans$ 个点才能覆盖所有区间相矛盾，故 $ans \le cnt$
综上所述 $ans=cnt$

核心代码

struct Range
{
    int l, r;
    bool operator< (const Range &W)const        
    {
        return r < W.r;         // 使sort()按右端点升序排序
    }
}range[N];

// main
sort(range, range + n);         // 按右端点升序排序

int res = 0, ed = -2e9;         // ed为无穷小
for (int i = 0; i < n; i ++ )
    if (ed < range[i].l)
    {
        // 找到一个无法由当前点覆盖的区间
        ed = range[i].r;         // 在数轴上放入新的点
        res ++ ;                // 更新数轴上点的个数
    }

区间分组

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

思路

左端点排序，从前往后处理每个区间
判断能否将其放到某个现有的组中
- 如果不存在，则开新组放入
- 如果存在，则放进该组并更新该组的最大右端点

证明

假设 $ans$ 是最优解，表示最少需要 $ans$ 个组； $cnt$ 是可行解，表示算法找到 $cnt$ 个组，显然有 $ans \le cnt$
考虑在开辟第 $cnt$ 个组的过程：算法此时已经开辟了 $cnt-1$ 个组，组内区间两两不相交，组间区间有交集，且当前遍历区间的左端点均小于各组所有区间中最大的右端点，即当前遍历的区间一定与各组区间相交，此时必须要开辟新的组放入新的区间，因此至少需要 $cnt$ 个组，即 $ans \ge cnt$
综上所述 $ans=cnt$

核心代码

struct Range
{
    int l, r;
    bool operator< (const Range &W)const
    {
        return l < W.l;
    }
}range[N];

// main
sort(range, range + n);         // 按左端点升序排序

priority_queue<int, vector<int>, greater<int>> heap;        // 小根堆，保存每组的最大右端点
for (int i = 0; i < n; i ++ )
{
    if (heap.empty() || range[i].l <= heap.top()) heap.push(range[i].r);    // 比所有组最大右端点都小
    else {
        heap.pop();                 // 合并到右端点最小的组，并更新该组的最大右端点
        heap.push(range[i].r);
    }
}

printf("%d\n", heap.size());        // 小根堆元素个数为组数

说明

range[i].l <= heap.top()等价于range[i].l <= min(heap)，表示比各组最大的右端点还要小，使得min的代价变为 $O(1)$
小根堆内并没有真的存储各组区间，而只是存储各组的最大右端点，当区间的左端点比各组右端点都小时，说明都冲突，需要开辟新组；否则只需把右端点最小的组的右端点更新成当前区间的右端点

区间覆盖

给定 $N$ 个闭区间 $[a_i,b_i]$ 以及一个线段区间 $[s,t]$ ，请你选择尽量少的区间，将指定线段区间完全覆盖。

思路

将所有区间按左端点从小到大排序
从前往后依次枚举每个区间，在所有能覆盖start的区间中选择右端点最大的区间，并将start更新成右端点的最大值

证明

假设 $ans$ 是最优解，表示最少需要 $ans$ 个区间； $cnt$ 是可行解，表示算法找到 $cnt$ 个区间满足覆盖，显然有 $ans \le cnt$
采用反证法证明ans≥cnt
- 假设最优解由 $k$ 个区间组成，各区间按右端点从小到大排序，右端点依次记为 $a_1,a_2,\cdots , a_k$ ，显然一定有 $t \le a_k$ ，否则最优解没有覆盖到线段区间 $[s,t]$ 的右端点 $t$ ，不满足覆盖条件
- 同理，假设算法求得m(m>k)个区间，各区间按右端点从小到大排序，右端点依次记为b1,b2,⋯,bk,⋯,bm，显然一定有bk<t≤bm
  - $t \le b_m$ 是为了满足覆盖条件
  - $b_k < t$ 是因为 $b_k$ 不是最后一个区间的端点，如果 $b_k \le t$ ，则
- 考虑最优解和贪心算法各自获得的第1个区间的右端点 $a_1$ 和 $b_1$ ，由于贪心算法选取右端点距离起点 $s$ 最大的区间，故一定有 $a_1 \le b_1$
- 贪心算法又以 $b_1$ 为起点，找一个右端点距离 $b_1$ 最大的区间，最优解选取的第2个区间的右端点 $a_2$ 不可能超过 $b_2$ ，否则存在一个区间的长度 $a_2 - a_1$ 大于 $b_2-b_1$ ，这与贪心算法矛盾，故一定有 $a_2 \le b_2$
- 同理一定有 $a_k \le b_k$ ，由于 $b_k < t$ ，故 $a_k < t$ ，这说明最优解没有覆盖线段区间 $[s,t]$ ，矛盾
- 故 $ans \ge cnt$
综上所述 $ans=cnt$

核心代码

struct Range
{
    int l, r;
    bool operator< (const Range &W)const
    {
        return l < W.l;
    }
}range[N];

// main
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);     // 选取距离起点最大的点（实际上只需看右端点的大小，因为起点是固定的，不影响max的选取）
        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);

Hoffman树

有 $n$ 个结点，每次合并两个结点需要消耗两个结点值之和的能量，求一种能量消耗最少的方案，使得所有结点合并成一个。

这里与合并石子的区别在于，合并石子只能合并相邻的两堆，而这里允许任意两个合并，并不一定是相邻的。

思路

每次选取最小的两个结点合并，直至全部合并成一个结点

证明

命题1：最小的两个点深度一定最深，且可以互为兄弟

命题2：最优树用一个非叶结点代替这两个结点后，依旧是最优树

命题1一定成立，否则交换两个点，一定会使总和减少，与最优树定义矛盾。

证明命题2等价于证明这是最优子结构。考虑等式 $f(k+1)=f(k)+a+b$ ，其中 $a$ 和 $b$ 是 $k+1$ 个结点构成的树中，值最小的两个。在 $k$ 个结点构成的树中，用一个新的叶节点代替了这两个结点。假设选取的不是 $a$ 和 $b$ ，显然新选结点的和会大于之前选的结点的和，故得到的不是最优树，因此这样构造的树一定是最优树，故满足最优子结构

核心代码

priority_queue<int, vector<int>, greater<int>> heap;        // 用小根堆存储元素，加快最小值的查找

int res = 0;
while (heap.size() > 1)         // 合并成1个
{
    int a = heap.top(); heap.pop();
    int b = heap.top(); heap.pop();
    res += a + b;
    heap.push(a + b);
}

排队打水

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

第 $1$ 个人等待的时间是 $0$ ，第 $2$ 个人等待的时间是 $t_1$ ，第 $3$ 个人等待的时间是 $t_1+t_2$ ，…，第 $n-1$ 个人等待的时间是 $t_1+t_1+\cdots + t_{n-2}$ ，第 $n$ 个人等待的时间是 $t_1+t_1+\cdots + t_{n-1}$

因此所有人的等待时间之和：
$0+(t_1)+(t_1+t_2)+(t_1+t_2+t_3)+\cdots + (t_1 + t_2 + \cdots + t_n-1)=t_1(n-1)+t_2(n-2)+\cdots + t_{n-1}$
思路

当 $t_1,t_2,\cdots , t_n$ 按升序排列时，所有人的等待时间最少。

证明

反证法：假设 $i<j$ 且 $t_i \gt t_j$ ，则可以交换二者，总时间会减少，说明原来不是最少的时间，矛盾。

核心代码

sort(t, t + n);         // 默认升序排序
reverse(t, t + n);      // 改成降序

long long res = 0;
for (int i = 0; i < n; i ++ ) res += t[i] * i;

货仓选址

数轴上有 $n$ 个点，在数轴上找一个点，使得那 $n$ 个点到这个点的距离之和最小

假设升序排序后的 $n$ 个数为 $x_1, x_2, \cdots,x_n$

总距离可表示为
$\begin{aligned} f\left( x \right) &=\left| x_1-x \right|+\left| x_2-x \right|+\cdots +\left| x_n-x \right| \\\ &=\left( \left| x_1-x \right|+\left| x_n-x \right| \right) +\left( \left| x_2-x \right|+\left| x_{n-1}-x \right| \right) +\cdots \\\ &\geqslant \left( x_n-x_1 \right) +\left( x_{n-1}-x_2 \right) +\cdots \end{aligned}$
由排序不等式知，当 $n$ 是奇数时，当且仅当在中位数取到等号；当 $n$ 是偶数，则当且仅当在两个中位数之间都能取到等号

核心代码

sort(a, a + n);

int res = 0;
for (int i = 0; i < n; i ++ ) res += abs(a[i] - a[n / 2]);      // q[n / 2]为中位数

说明

如果 $n$ 是奇数，则n / 2是中位数下标
如果 $n$ 是偶数，则n / 2是靠左的中位数下标，由于在 $a_{n/2}$ ~ $a_{n/2 + 1}$ 之间（包括端点）都能取到等号，故可以和奇数一致选取下标为n/2的数

耍杂技的牛

有 $n$ 头牛，第 $i$ 头牛的重量为 $w_i$ ，强壮值为 $s_i$ ，一头牛的危险系数定义为这头牛上边的重量之和减去这头牛的强壮值，求一种顺序，使得 $n$ 头牛最大的危险系数最小

思路

按 $w_i+s_i$ 升序排序

证明

假设 $best$ 是最优解，表示最小的危险系数； $ans$ 是可行解，表示算法找到危险系数，显然有 $best \le ans$

反证法证明 $best \ge ans$ 。假设 $w_i+s_i>w_{i+1} + s_{i+1}$ ，可得下表

各项同时去掉 $w_1+w_2+\cdots +w_{i-1}$ ，得

各项同时加上 $s_i + s_{i+1}$ ，得

由于 $w_i+s_i \ge s_i$ 且 $w_i+s_i \ge w_{i+1}+s_{i+1}$ ，故 $w_i+s_i \ge \max\{s_i, w_{i+1}+s_{i+1} \}$ ，进而 $\max \{ s_{i+1}, w_i + s_i \} \ge \max\{s_i, w_{i+1}+s_{i+1} \}$

故交换后 $n$ 头牛的最大危险系数要么减少，要么不变，总之不会增加

假设最优解有满足这样条件的两头牛，则把它们交换后，最大危险系数会下降，与最优解的定义矛盾，故最优解一定满足这样按 $w_i+s_i$ 升序排序的条件，即 $best \ge ans$

综上所述 $best=ans$

核心代码

typedef pair<int, int> PII;
PII cow[N];

// 读入
scanf("%d%d", &w, &s);
cow[i] = {w + s, w};    // first为二者和，second为重量

// main
sort(cow, cow + n);     // 按w+s升序排序

int res = -2e9, sum = 0;        // 初始化为无穷小
for (int i = 0; i < n; i ++ )
{
    int s = cow[i].first - cow[i].second, w = cow[i].second;    // 读取s和w
    res = max(res, sum - s);        // 更新最大危险系数
    sum += w;                      // 第0~i头牛的重量之和（由上到下）
}