C++
备战CSP-J初赛21天打卡计划。DAY13-常见贪心算法类型
mrhowe SU @ 2024-9-10 14:31:19

贪心

近4年考察：

	题号	题型	分值
2020	第20题	完善程序	15分
2021	第20题	完善程序	15分

难易度：中等

2024年备考建议

贪心思想是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，如果要得到整个问题的最优答案，那么每一步都要尽可能的得到最优的答案。

首先初赛必然无法考察贪心的证明。聚焦在贪心的经典题型，又因为贪心算法，方便与其他知识点关联，比如结构体排序后贪心，比如二分答案里做贪心，所以往往代码量和思维度都适合放在压轴题的位置。

解决初赛中的贪心问题，先要熟悉贪心的常见题型。

常见题型

最常见的贪心有两种。

「我们将 XXX 按照某某顺序排序，然后按某种顺序（例如从小到大）选择。」。
「我们每次都取 XXX 中最大/小的东西，并更新 XXX。」（有时「XXX 中最大/小的东西」可以优化，比如用优先队列维护）

第二种方式基本要用到“优先队列”这种数据结构，在CSP-J的组别里不可能出现，因为只需要准备第一种贪心。

傻瓜贪心

举个栗子 USACO DEC07 超级书架

题意是给定n个正整数和一个正整数k，问最少选择多少个正整数使得它们之和大于等于k。

很显然这类问题的求解，就是排序 + 统计。

//题目的完整代码
#include <bits/stdc++.h>
using namespace std;

int main() {
    //定义 n 表示奶牛的头数， 定义 B 表示书架高度，
    //接下来 读入 n 行整数，每行整数表示 一头奶牛的身高
    int n, B, h[20005];
    cin >> n >> B;
    for (int i = 0; i < n; i++) cin >> h[i];
    
    //一、按照从小到大做排序
    sort(h, h + n);
    
    //二、选择身高前cnt高的牛
    int cnt = 0, sum = 0;
    for (int i = n-1; i >= 0; i--) {  // 遍历所有奶牛（从高的开始）
        sum += h[i];                  // 把第i头牛落到叠的上面
        cnt++;                        // 牛的数量+1
        if (sum >= B) break;          // 如果达到了书架高度 那么就退出循环了
    }
    cout << cnt;
    return 0;
}

哈夫曼树

哈夫曼树是一种二叉树，用于数据压缩。它的构建方式是通过对一个数据集中的元素进行频率统计，然后将频率较小的元素放在树的底部（远端），频率较大的元素放在树的顶部（近端），以此来减小数据的存储空间。

在哈夫曼树中，从根节点到某个叶子节点的路径上的编码，就是该叶子节点所表示字符的哈夫曼编码。

构造哈夫曼树

哈夫曼树的构建可以使用贪心算法来实现，时间复杂度为O(nlog⁡n)O(nlogn)，其中nn为数据集中元素的个数。

具体构建方式是，首先将所有元素按照出现频率从小到大排序，然后选取频率最小的两个元素作为左右子节点，将它们的频率相加作为父节点的频率，然后将父节点插入到排序后的元素列表中，重复上述步骤直到只剩下一个根节点为止。最后，从根节点开始递归遍历哈夫曼树，将每个叶子节点所表示的字符及其对应的哈夫曼编码存储起来。

假设有如下8个字符及对应的权值：

字符	权值
A	2
B	3
C	7
D	10
E	11
F	13
G	14
H	20

我们可以按照以下步骤构造哈夫曼树：

将所有节点按照权值从小到大排序，得到 2,3,7,10,11,13,14,20。
选取权值最小的两个节点2和3，将它们合并为一个新节点，其权值为2+3=5。这个新节点代表的子树有2和3两个节点。
将得到的新节点5插入集合中，集合变为 5,7,10,11,13,14,20。
选取权值最小的两个节点5和7，将它们合并为一个新节点，其权值为5+7=12。这个新节点代表的子树有5和7两个节点。
将得到的新节点12插入集合中，集合变为 10,11,12,13,14,20。
选取权值最小的两个节点10和11，将它们合并为一个新节点，其权值为10+11=21。这个新节点代表的子树有10和11两个节点。
将得到的新节点21插入集合中，集合变为 12,13,14,20,21。
选取权值最小的两个节点12和13，将它们合并为一个新节点，其权值为12+13=25。这个新节点代表的子树有12和13两个节点。
将得到的新节点25插入集合中，集合变为 14,20,21,25。
选取权值最小的两个节点14和20，将它们合并为一个新节点，其权值为14+20=34。这个新节点代表的子树有14和20两个节点。
将得到的新节点34插入集合中，集合变为 21, 25, 34。
选取权值最小的两个节点21和25，将它们合并为一个新节点，其权值为21+25=46。这个新节点代表的子树有21和25两个节点。
将得到的新节点46插入集合中，集合变为 34, 46。
选取权值最小的两个节点34和46，将它们合并为一个新节点，其权值为34+46=80。这个新节点代表的子树有34和46两个节点。
哈夫曼树构建完成，根节点的权值为80，左子树的权值为34，右子树的权值为46。

下图为本例的哈夫曼树：

构建完哈夫曼树后，从哈夫曼树的根节点开始，遍历左子树的路径为0，遍历右子树的路径为1，则每个叶子节点对应的字符编码为从根节点到该叶子节点经过的路径上的0和1序列。注意，由于哈夫曼树是一棵前缀编码树，因此每个字符的编码不会是另一个字符编码的前缀。

本例中所有节点对应的编码如下：

字符	权值	编码
A	2	11000
B	3	11001
C	7	111
D	10	100
E	11	101
F	13	111
G	14	00
H	20	01

区间问题

最大不相交区间数量

举个栗子 leetcode 435 无重叠的子区间

给定一个区间的集合 A ，其中 A[i] = [starti, endi] 。返回需要移除区间的最小数量，使剩余区间互不重叠。

//题目的完整代码
struct Intervals{
    int st, ed;
} a[100005];

bool cmp(Intervals x, Intervals y) {
    return x.ed < y.ed;
}

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int n = intervals.size();
        for (int i = 0; i < n; i++) {
            a[i].st = intervals[i][0];
            a[i].ed = intervals[i][1];
        }

        sort(a, a + n, cmp);

        int sum = 1, st = a[0].st, ed = a[0].ed;
        for (int i = 1; i < n; i++) {
            if (a[i].st >= ed) {
                sum++;
                st = a[i].st;
                ed = a[i].ed;
            }
        }
        return n - sum;
    }
};

区间分组

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

我们可以把所有开始时间和结束时间排序，遇到开始时间就把需要的教室加1，遇到结束时间就把需要的教室减1,在一系列需要的教室个数变化的过程中，峰值就是多同时进行的活动数，也是我们至少需要的教室数。

//题目的完整代码
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

int n;
int b[2*N], idx;

int main(){
    scanf ("%d", &n);
    for (int i = 0; i < n; i ++) {
        int l, r;
        scanf("%d %d", &l, &r);
        b[idx ++] = l * 2;//标记左端点为偶数。
        b[idx ++] = r * 2 + 1;// 标记右端点为奇数。
    }

    sort(b, b + idx);

    int res = 1, t = 0;
    for (int i = 0; i < idx; i ++){
        if(b[i] % 2 == 0) t ++;
        else t --;
        res = max(res, t);
    }
    printf ("%d\n", res);
    return 0;
}

最小区间覆盖

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

输出最少区间数，如果无法完全覆盖则输出 −1。

分析：第一步，将所有区间按照左端点从小到大进行排序

第二步，从前往后枚举每个区间，在所有能覆盖start的区间中，选择右端点的最大区间，然后将start更新成右端点的最大值

//题目的完整代码
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

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;
}

找拐点

求一个最长序列，使得该序列的任意三个相邻元素，中间的元素是三个中最大的，或者是最小的（最长波浪序列）

//题目的完整代码
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> h(n);
    for (int i = 0; i < n; i++) cin >> h[i];

    int x = 0;
    while (x+1 < n and h[x+1] == h[x]) ++x; // 开始如果一段相同的则去重，取哪盆都一样

    bool f = false;
    if (h[x+1] > h[x]) f = true; // 确定一开始是上升还是下降的

    int ans = 1;
    for (int i = x+1; i < n; ++i) {
        if (i == n-1) ans++; // 结尾没有拐点直接加
        else if (f && h[i+1] < h[i]) { ans++; f = 0; } // 找到波峰
        else if (!f && h[i+1] > h[i]) { ans++; f = 1; } // 找到波谷
    }

    cout << ans << '\n';

    return 0;
}

历年真题

2020CSP普及组-20题-完善程序题

1 	#include <iostream>
2 
3 	using namespace std;
4 
5 	const int MAXN = 5000;
6 	int n, m;
7 	struct segment { int a, b; } A[MAXN];
8 
9 	void sort() // 排序
10	{
11	  for (int i = 0; i < n; i++)
12	  for (int j = 1; j < n; j++)
13	  if (①)
14		  {
15			segment t = A[j];
16			②
17		  }
18	}
19
20	int main()
21	{
22	  cin >> n >> m;
23	  for (int i = 0; i < n; i++)
24		cin >> A[i].a >> A[i]・b;
25	  sort();
26	  int p = 1;
27	  for (int i = 1; i < n; i++)
28		if (③)
29		  A[p++] = A[i];
30	  n = p;
31	  int ans =0, r = 0;
32	  int q = 0;
33	  while (r < m)
34	  {
35		while (④)
36		  q++;
37		⑤;
38		ans++;
39	  }
40	  cout << ans << endl;
41	  return 0;
42	}

1)①处应填（）

2)②处应填（）

3)③处应填（）

4)④处应填（）

5)⑤处应填（）

1.

[ ] A. A[j].b>A[j-1].b

[ ] B. A[j].a<A[j-1].a

[ ] C. A[j].a>A[j-1].a

[ ] D. A[j].b<A[j-1].b
2. [ ] A. A[j+1]=A[j];A[j]=t;

[ ] B. A[j-1]=A[j];A[j]=t;

[ ] C. A[j]=A[j+1];A[j+1]=t;

[ ] D. A[j]=A[j-1];A[j-1]=t;
3. [ ] A. A[i].b>A[p-1].b

[ ] B. A[i].b<A[i-1].b

[ ] C. A[i].b>A[i-1].b

[ ] D. A[i].b<A[p-1].b
4. [ ] A. q+1<n&&A[q+1].a<=r

[ ] B. q+1<n&&A[q+1].b<=r

[ ] C. q<n&&A[q].a<=r

[ ] D. q<n&&A[q].b<=r
5. [ ] A. r=max(r,A[q+1].b)

[ ] B. r=max(r,A[q].b)

[ ] C. r=max(r,A[q+1].a)

[ ] D. q++

2021CSP普及组第20道题完善程序题

（矩形计数） 平面上有 n 个关键点，求有多少个四条边都和 x 轴或者 y 轴平行的矩形，满足四个顶点都是关键点。给出的关键点可能有重复，但完全重合的矩形只计一次。

1 	#include <stdio.h>
2 
3 	struct point {
4 		int x, y, id;
5 	};
6 
7 	int equals(struct point a, struct point b){
8 		return a.x == b.x && a.y == b.y;
9 	}
10
11	int cmp(struct point a, struct point b){
12		return  ①; 
13	}
14
15	void sort(struct point A[], int n){
16		for (int i = 0; i < n; i++)
17			for (int j = 1; j < n; j++)
18				if (cmp(A[j], A[j - 1])){
19					struct point t = A[j];
20					A[j] = A[j - 1];
21					A[j - 1] = t;
22				}
23	}
24
25	int unique(struct point A[], int n){
26		int t = 0;
27		for (int i = 0; i < n; i++)
28			if (②)
29				A[t++] = A[i];
30		return t;
31	}
32
33	int binary_search(struct point A[], int n, int x, int y){
34		struct point p;
35		p.x = x;
36		p.y = y;
37		p.id = n;
38		int a = 0, b = n - 1;
39		while(a < b){
40			int mid = ③;
41			if (④)
42				a = mid + 1;
43			else 
44				b = mid; 
45		}
46			return equals(A[a], p);
47	}
48
49	#define MAXN 1000
50	struct point A[MAXN];
51
52	int main(){
53		int n;
54		scanf("%d", &n);
55		for (int i = 0; i < n; i++){
56			scanf("%d %d", &A[i].x, &A[i].y);
57			A[i].id = i;
58		}
59		sort(A, n);
60		n = unique(A, n);
61		int ans = 0;
62		for (int i = 0; i < n; i++)
63			for (int j = 0; j < n; j++)
64			if ( ⑤ && binary_search(A, n, A[i].x, A[j].y) && binary_search(A, n, A[j].x, A[i].y)){
65							ans++;
66			}
67		printf("%d\n", ans); 
68		return 0;
69	}

试补全枚举算法。

1. [ ] A. a.x != b.x ? a.x < b.x : a.id < b.id

[ ] B. a.x != b.x ? a.x < b.x : a.y < b.y

[ ] C. equals(a, b) ? a.id < b.id : a.x < b.x

[ ] D. equals(a, b) ? a.id < b.id : (a.x != b.x ? a.x < b.x : a.y < b.y)

2. [ ] A. i == 0 || cmp(A[i], A[i - 1])

[ ] B. t == 0 || equals(A[i], A[t - 1])

[ ] C. i == 0 || !cmp(A[i], A[i - 1])

[ ] D. t == 0 || !equals(A[i], A[t - 1])

3. [ ] A. b - (b - a) / 2 + 1

[ ] B. (a + b + 1) >> 1

[ ] C. (a + b) >> 1

[ ] D. a + (b - a + 1) / 2

4. [ ] A. !cmp(A[mid], p)

[ ] B. cmp(A[mid], p)

[ ] C. cmp(p, A[mid])

[ ] D. !cmp(p, A[mid])

5. [ ] A. A[i].x == A[j].x

[ ] B. A[i].id < A[j].id

[ ] C. A[i].x == A[j].x && A[i].id < A[j].id

[ ] D. A[i].x < A[j].x && A[i].y < A[j].y

mrhowe SU @ 2024-9-10 14:37:22
2020CSP普及组第20道题完善程序题

正确答案：
- 第一空(3分)： B
- 第二空(3分)： D
- 第三空(3分)： A
- 第四空(3分)： A
- 第五空(3分)： B
2021CSP普及组第20道题完善程序题
- 第一空(3分)： B
- 第二空(3分)： D
- 第三空(3分)： C
- 第四空(3分)： B
- 第五空(3分)： D

备战CSP-J初赛21天打卡计划。DAY13-常见贪心算法类型

贪心

2024年备考建议

常见题型

傻瓜贪心

哈夫曼树

构造哈夫曼树

区间问题

最大不相交区间数量

区间分组

最小区间覆盖

找拐点

历年真题

1 条评论

状态

开发

支持

备战CSP-J初赛21天打卡计划。DAY13-常见贪心算法类型

贪心

2024年备考建议

常见题型

傻瓜贪心

哈夫曼树

构造哈夫曼树

区间问题

最大不相交区间数量

区间分组

最小区间覆盖

找拐点

历年真题

1 条评论

状态

开发

支持

还没有账户？

登录