贪心算法刷题笔记

贪心

定义：贪心是求解一类最优化问题的方法，它总是考虑在当前状态下局部最优（或较优） 的策略，来使全局的结果达到最优（或较优）。显然，如果采取较优而非最优的策略（最优策略可能不存在或是不易想到），得到的全局结果也无法使用最优的。而要获得最优结果，则要求中间的每步策略都是最优的，因此严谨使用贪心法来求解最优化问题需要对采取的策略进行证明，证明的一般思路是使用反证法及数学归纳法，即假设策略不能导致最优解，然后通过系列推导来得到矛盾，以此证明策略是最优的，最后用数学归纳法保证是全局最优。不过平常使用无须严格证明。因此，如果在想到某个似乎可行的策略，并且自己无法举出反例，那就勇敢的实现它。

堆优化

• 理论

堆（Heap）是一种特殊的树形数据结构，通常分为两种：最大堆和最小堆。其中最大堆的特点是，每个节点的值都大于或等于其子节点的值；最小堆的特点是，每个节点的值都小于或等于其子节点值。
堆的主要算法有以下几种：

1. 堆的建立：将一个无序的数据序列构建成一个堆的过程称为堆的建立。堆的建立通常采用自下而上的方式进行，即从最后一个非叶子节点开始，依次向上调整各个节点的位置，使其满足堆的性质。
2. 堆的插入：在堆中插入一个新元素的过程称为堆的插入。堆的插入通常采用自下而上的方式进行，即将新元素插入到堆的末尾，然后向上调整该元素的位置，使其满足堆的性质。
3. 堆的删除：在堆中删除一个元素的过程称为堆的删除。堆的删除通常采用自上而下的方式进行，即将堆顶元素删除，并将堆的最后一个元素放到堆顶，然后向下调整该元素的位置，使其满足堆的性质。
4. 堆的排序：利用堆的特性，可以将一个无序的数据序列进行排序，称为堆排序。堆排序的基本思路是，将数据序列构建成一个最大堆或最小堆，然后依次取出堆顶元素，将其放到有序区间的末尾，再重新调整堆的结构。通过多次这样的操作，最终可以得到一个有序的数据序列。
   需要注意的是，堆的算法中，通常采用的是完全二叉树的结构，因此堆的操作通常可以通过数组来实现。同时，由于堆的特性，可以在O(log n)的时间复杂度内进行堆的插入、删除和排序等操作，因此堆在实际应用中具有广泛的应用。

$c++$中$stl$自带堆——$priority\_queue$默认最大堆
$make\_heap()$，$greater<int>()$小顶堆，$less<int>()$大顶堆

#include 
#include 
using namespace std;
// 最大堆的实现
class MaxHeap {
private:
    vector<int> heap; // 使用 vector 存储堆
    void heapify(int i) { // 将节点 i 进行向下调整
        int n = heap.size();
        int left = 2 * i + 1, right = 2 * i + 2;
        int max_index = i;
        if (left < n && heap[left] > heap[max_index]) {
            max_index = left;
        }
        if (right < n && heap[right] > heap[max_index]) {
            max_index = right;
        }
        if (max_index != i) {
            swap(heap[i], heap[max_index]);
            heapify(max_index);
        }
    }
public:
    MaxHeap() {}
    MaxHeap(vector<int> v) { // 构造函数，将 vector 转换为堆
        heap = v;
        for (int i = heap.size() / 2 - 1; i >= 0; i--) {
            heapify(i);
        }
    }
    void push(int x) { // 插入元素 x
        heap.push_back(x);
        int i = heap.size() - 1;
        int parent = (i - 1) / 2;
        while (i > 0 && heap[i] > heap[parent]) {
            swap(heap[i], heap[parent]);
            i = parent;
            parent = (i - 1) / 2;
        }
    }
    void pop() { // 删除堆顶元素
        int n = heap.size();
        swap(heap[0], heap[n - 1]);
        heap.pop_back();
        heapify(0);
    }
    int top() { // 获取堆顶元素
        return heap[0];
    }
    bool empty() { // 判断堆是否为空
        return heap.empty();
    }
    int size() { // 获取堆中元素的个数
        return heap.size();
    }
};
int main() {
    MaxHeap h;
    h.push(3);
    h.push(2);
    h.push(1);
    h.push(4);
    while (!h.empty()) {
        cout << h.top() << " ";
        h.pop();
    }
    cout << endl; // 输出 4 3 2 1
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

一般贪心

矩阵消除游戏

题目描述

链接：牛妹在玩一个名为矩阵消除的游戏，矩阵的大小是n行m列，第i行第j列的单元格的权值为a_i,j，牛妹可以进行k个回合的游戏，在每个回合，牛妹可以选择一行或者选择一列，然后将这一行或者这一列的所有单元格中的权值变为0，同时牛妹的分数会加上这一行或者这一列中的所有单元格的权值的和。
牛妹想最大化她的得分，球球你帮帮她吧！

输入描述

第一行三个整数n,m,k
接下来n行每行m个整数表示矩阵中各个单元格的权值

输出描述

输出一个整数表示牛妹能获得的最大分数。

示例一
输入

3 3 2
101 1 102
1 202 1
100 8 100

输出

414

备注

1≤n,m≤15
1≤a_i,j≤1e6
1≤k≤n∗m

思路

• 这是一道不算太难的贪心、枚举题（但是自己做了很久，还WA了很多次）
• 我第一次做的时候想的是：如果我每次贪心的选剩下的图中最大的一行或者一列，然后把这一行（列）抹为0 ，但是很明显，这个方法的错误在于你抹了0会对后面的贪心选择造成影响
• 使用01串枚举（二进制枚举）
• 用行开始枚举

题解

#include
using namespace std;
int n,m,k,a[20][20];
long long sh[20],sl[20],ans;
bool b[20];                          //记录被选中的行的序号
bool cmp(int a,int b) {
    return a>b;
}
int deal(int x) {
    memset(b,0,sizeof b);
    int cnt=0,i=1;
    while(x) {
        if(x&1) {                    //检测最后一个数字是否为1，如果为1就++cnt，并记录行序号i
            ++cnt;
            b[i]=1;
        }
        x>>=1;              //右移一位，相当于从右往左依次检测
        ++i;
    }
    return cnt;
}
int main() {
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;++i)
    for(int j=1;j<=m;++j) {
        scanf("%d",&a[i][j]);
        sh[i]+=a[i][j];
    }
    if (k > n) k=n;
    if (k > m) k=m;
    int tmp=(1<<n)-1;    //枚举的总个数为2的n次方个（对于每一行有2个选择，选中或不选中）
    for(int x=0;x<=tmp;++x) { //要从0开始，因为一行也不选需要纳入考量范围
        int numh=deal(x);
        int numl=k-numh;
        if(numl<0) continue;
        long long  sum=0;
        for (int i = 1; i <= n; i++)
            if(b[i]) sum+=sh[i];           //被选中的行，加起来
        memset(sl, 0, sizeof(sl));
        for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(!b[i]) sl[j]+=a[i][j];           //从列开始汇总，在行中被选用的不纳入
        sort(sl+1, sl+1+m,cmp);      //从大到小排序，贪心选择值最大的列
        for(int i=1;i<=numl;++i) sum += sl[i];
        ans=max(ans,sum);
    }
    printf("%lld\n", ans);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

[蓝桥杯 2021 省 AB2] 负载均衡

有 $n$ 台计算机，第 $i$ 台计算机的运算能力为 $v_i$ 。

有一系列的任务被指派到各个计算机上，第 $i$ 个任务在 $a_i$ 时刻分配，指定计算机编号为 $b_i$, 耗时为 $c_i$ 且算力消耗为 $d_i$。如果此任务成功分配，将立刻开始运行, 期间持续占用 $b_i$ 号计算机 $d_i$ 的算力, 持续 $c_i$ 秒。

对于每次任务分配，如果计算机剩余的运算能力不足则输出 $-1$，并取消这次分配，否则输出分配完这个任务后这台计算机的剩余运算能力。

输入格式

输入的第一行包含两个整数 $n,m$，分别表示计算机数目和要分配的任务数。

第二行包含 $n$ 个整数 $v_1,v_2,\cdots v_n$，分别表示每个计算机的运算能力。

接下来 $m$ 行每行 $4$ 个整数 $a_i,b_i,c_i,d_i$，意义如上所述。数据保证 $a_i$ 严格递增，即 $a_i<a_{i+1}$ 。

输出格式

输出 $m$ 行，每行包含一个数，对应每次任务分配的结果。

样例输入 #1

2 6
5 5
1 1 5 3
2 2 2 6
3 1 2 3
4 1 6 1
5 1 3 3
6 1 3 4
1
2
3
4
5
6
7
8

样例输出 #1

2
-1
-1
1
-1
0
1
2
3
4
5
6

提示

【样例说明】

时刻 $1$，第 $1$ 个任务被分配到第 $1$ 台计算机，耗时为 $5$，这个任务时刻 $6$ 会结束, 占用计算机 $1$ 的算力 $3$。

时刻 $2$，第 $2$ 个任务需要的算力不足，所以分配失败了。

时刻 $3$，第 $1$ 个计算机仍然正在计算第 $1$ 个任务，剩余算力不足 $3$，所以失败。

时刻 $4$，第 $1$ 个计算机仍然正在计算第 $1$ 个任务，但剩余算力足够，分配后剩余算力 $1$。

时刻 $5$，第 $1$ 个计算机仍然正在计算第 $1$，$4$ 个任务，剩余算力不足 $4$，失败。

时刻 $6$，第 $1$ 个计算机仍然正在计算第 $4$ 个任务，剩余算力足够，且恰好用完。

【评测用例规模与约定】

对于 $20\%$ 的评测用例, $n,m\le 200$。

对于 $40\%$ 的评测用例, $n,m\le 2000$。

对于所有评测用例, $1\le n,m\le 2\times 10^5,1\le a_i,c_i,d_i,v_i\le 10^9,1\le b_i\le n$。

蓝桥杯 2021 第二轮省赛 A 组 H 题（B 组 I 题）。

思路

• 刚开始不难想到纯模拟，但是看到数据规模，感觉这题需要一些优化方法（堆优化）（堆操作可以降低时间开销）

题解

#include 
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 200010;
int n, m;
int s[N];
priority_queue<PII, vector<PII>, greater<PII>> q[N];//对于queue和stack的操作更快（在没有频繁访问内部元素时）
int main(){
	cin >> n >> m;
	for (int i = 1; i <= n; i++)cin >> s[i];
	while (m--){
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		while (q[b].size() && q[b].top().x <= a){
			s[b] += q[b].top().y;
			q[b].pop();
		}
		if (s[b] < d) puts("-1");
		else{
			q[b].push({ a + c, d });
			s[b] -= d;
			cout << s[b] << endl;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

推公式

[USACO 2007 Jan S]Protecting the Flower

思路

• 初看题目，知道minimize意味着要使用贪心算法，每一步都要作出小的选择
• 推公式 —— 任意选出两头牛进行贪心排序，可以看到有2种排法（a,b、b,a）
  1. （a，b）那么第二头牛的破坏量就是t_a*d_b*2
  2. （a，b）那么第二头牛的破坏量就是t_b*d_a*2
  3. 比较两个排法即可
• 用数学归纳法推广到整个数组

题解

#include 
using namespace std;
pair<int,int> p[100005];
bool cmp(pair<int,int> a,pair<int,int> b){
    return a.first*b.second<b.first*a.second;
}
int main(){
    int n;
    cin >>n;
    for(int i=0;i<n;++i){
        cin>>p[i].first>>p[i].second;
    }
    sort(p,p+n,cmp);
    long long sum=0, ans=0;
    for(int i=0;i<n;++i){
        ans+=sum*p[i].second;
        sum+=p[i].first;
    }
    ans*=2;
    cout <<ans<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

注意对pair使用sort排序，默认比较pair.first，也可以自己写bool函数自定义

按位贪心

兔子的区间密码

题目描述

有一只可爱的兔子被困在了密室了，密室里有两个数字，还有一行字：
只有解开密码，才能够出去。
可爱的兔子摸索了好久，发现密室里的两个数字是表示的是一个区间[L,R]
而密码是这个区间中任意选择两个(可以相同的)整数后异或的最大值。
比如给了区间[2,5] 那么就有2 3 4 5这些数，其中 2 xor 5=7最大 所以密码就是7。
兔子立马解开了密室的门，发现门外还是一个门，而且数字越来越大，兔子没有办法了，所以来求助你。
提示：异或指在二进制下一位位比较，相同则 0 不同则 1
例如2=(010)₂， 5=(101)₂
​所以2 xor 5=(111)₂=7

输入描述

第一行一个数 T，表示数据组数。
接下来 T 行，每行两个数 L，R, 表示区间[L,R]

输出描述

输出共T行每行一个整数，表示[L,R]的密码

示例一
输入

5
1 10
2 3
3 4
5 5
2 5

输出

15
1
7
0
7

备注

对于30%的数据
1 ≤ T ≤ 10
0 ≤ L ≤ R ≤ 100
对于另外10%的数据
L=R
对于70%的数据
1 ≤ T ≤ 10
0 ≤ L ≤ R ≤ 50000
对于100%的数据
1 ≤ T ≤ 10000
0 ≤ L ≤ R ≤ 1018
(对于100%的数据) 输入数据较大，请使用快速读入。

思路

• 这道题没有好的方法就不简单，但是找到好的切入点就比较清晰了
• L<=R，那么换成二进制就会有2种结果：
  1. L的位数=R的位数（L=（1000）₂，R=（1011）₂）
  2. L的位数比R的小（L=（100）₂，R=（1000）₂）
• 可以看出，在这个区间上要找到异或值最大的数就是要找不同的位数最大的数。如果我们比较L和R的每一位，当发现第一个不同的数字时，就可以确定结果了
• 假设确定的位置数为i，那么，2ⁱ⁺¹-1——就能造出一个含1最多的数（0111……），而这个区间内肯定存在相应的含0最多的数（0000……），此时，这两个数异或就得到区间最大值
• 题目中提到了快速读入，但是这道题就算没用快速读入也可以AC。不代表不需要知道快速读入😪
  要使用 inline，因为一般要使用到 快速读入 的时候都会频繁调用，这段代码考虑到了负数

inline int read(){
    int x=0,y=1;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') y=-1;c=getchar();}
    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*y;
}
1
2
3
4
5
6

题解

#include
using namespace std;
int t,i;
typedef long long ll;
ll l,r;
int main(){
    scanf("%d",&t);
    while(t--){
        cin>>l>>r;
        for(i=63;i>=0;--i) if((l>>i)!=(r>>i)) break;      //无需特判，当L=R时，i=-1，结果输出的是0
        cout<<(1ll<<(i+1))-1<<endl;                       1ll指long long型的1
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

起床困难综合症

题目描述

21 世纪，许多人得了一种奇怪的病：起床困难综合症，其临床表现为：起床难，起床后精神不佳。作为一名青春阳光好少年，atm 一直坚持与起床困难综合症作斗争。通过研究相关文献，他找到了该病的发病原因：在深邃的太平洋海底中，出现了一条名为 drd 的巨龙，它掌握着睡眠之精髓，能随意延长大家的睡眠时间。正是由于 drd 的活动，起床困难综合症愈演愈烈，以惊人的速度在世界上传播。为了彻底消灭这种病，atm 决定前往海底，消灭这条恶龙。
历经千辛万苦，atm 终于来到了 drd 所在的地方，准备与其展开艰苦卓绝的战斗。drd 有着十分特殊的技能，他的防御战线能够使用一定的运算来改变他受到的伤害。具体说来，drd 的防御战线由 𝑛 扇防御门组成。每扇防御门包括一个运算 op 和一个参数 𝑡，其中运算一定是 OR,XOR,AND 中的一种，参数则一定为非负整数。如果还未通过防御门时攻击力为 𝑥 ，则其通过这扇防御门后攻击力将变为 𝑥 op 𝑡 。最终drd 受到的伤害为对方初始攻击力 𝑥 依次经过所有 𝒏 扇防御门后转变得到的攻击力。
由于atm 水平有限，他的初始攻击力只能为 0 到 𝑚 之间的一个整数（即他的初始攻击力只能在 0, 1, … , 𝑚 中任选，但在通过防御门之后的攻击力不受 𝑚 的限制）。为了节省体力，他希望通过选择合适的初始攻击力使得他的攻击能让 drd受到最大的伤害，请你帮他计算一下，他的一次攻击最多能使 drd 受到多少伤害

输入描述

第 1 行包含2 个整数，依次为 𝑛, 𝑚 ，表示drd 有 𝑛 扇防御门，atm 的初始攻击力为 0 到 𝑚 之间的整数。
接下来 𝑛 行，依次表示每一扇防御门。每行包括一个字符串 op 和一个非负整数 𝑡，两者由一个空格隔开，且 op 在前， 𝑡 在后，op 表示该防御门所对应的操作，𝑡 表示对应的参数。

输出描述

输出一行一个整数，表示atm 的一次攻击最多使 drd 受到多少伤害

示例一
输入

3 10
AND 5
OR 6
XOR 7

输出

1

说明

atm 可以选择的初始攻击力为 0,1, … ,10。
假设初始攻击力为 4，最终攻击力经过了如下计算
4 AND 5 = 4
4 OR 6 = 6
6 XOR 7 = 1
类似的，我们可以计算出初始攻击力为 1,3,5,7,9 时最终攻击力为 0，初始攻击力为 0,2,4,6,8,10 时最终攻击力为 1，因此atm 的一次攻击最多使 drd 受到的伤害值为 1

备注

思路

• 首先简化题目的意思——给出初始区间、一段操作符和操作数，由初始区间内的数经过操作后能得到的最大值
• 明显需要使用二进制计算。但如果枚举初始区间内每一个数进行操作，时间复杂度O(_mn)，可能会TLE
• 可以取特殊的数0(0000……)₂，-1(111111……)₂（都是32位，因为int），当0经过所有的操作后，各个二进制位上是1的位置就应保留（为了让结果最大）。-1经过所有操作后，二进制位上是1的也保留（但是要限制<=m）

题解

#include
using namespace std;
int n,m,t,a=0,b=-1,ans=0;
char op[5];
int main(){
    scanf("%d%d",&n,&m);
    while(n--){
        scanf("%s%d",op,&t);
        if(op[0]=='A') a&=t,b&=t;
        else if(op[0]=='X') a^=t,b^=t;
        else a|=t,b|=t;
    }
    for(int i=1<<29;i;i>>=1){
        if(a&i) ans|=i;
        else if((b&i)&&(i<=m))ans|=i;
    }
    printf("%d",ans);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

[蓝桥杯 2021 省 A] 异或数列

Alice 和 Bob 正在玩一个异或数列的游戏。初始时，Alice 和 Bob 分别有一个整数 $a$ 和 $b$, 有一个给定的长度为 $n$ 的公共数列 $X_1,X_2,\cdots ,X_n$ 。

Alice 和 Bob 轮流操作，Alice 先手，每步可以在以下两种选项中选一种:

选项 1: 从数列中选一个 $X_i$ 给 Alice 的数异或上, 或者说令 $a$ 变为 $a\oplus X_i$ 。（其中 $\oplus$ 表示按位异或）

选项 2: 从数列中选一个 $X_i$ 给 Bob 的数异或上，或者说令 $b$ 变为 $b\oplus X_i$ 。

每个数 $X_i$ 都只能用一次, 当所有 $X_i$ 均被使用后（$n$ 轮后）游戏结束。游戏结束时, 拥有的数比较大的一方获胜，如果双方数值相同，即为平手。

现在双方都足够聪明，都采用最优策略，请问谁能获胜?

输入格式

每个评测用例包含多组询问。询问之间彼此独立。

输入的第一行包含一个整数 $T$，表示询问数。

接下来 $T$ 行每行包含一组询问。其中第 $i$ 行的第一个整数 $n_i$ 表示数列长度，随后 $n_i$ 个整数 $X_1,X_2,\cdots ,X_{n_i}$ 表示数列中的每个数。

输出格式

输出 $T$ 行，依次对应每组询问的答案。

每行包含一个整数 $1$、$0$ 或 $-1$ 分别表示 Alice 胜、平局或败。

样例输入 #1

4
1 1
1 0
2 2 1
7 992438 1006399 781139 985280 4729 872779 563580
1
2
3
4
5

样例输出 #1

1
0
1
1
1
2
3
4

提示

对于所有评测用例, $1\le T\le 2\times 10^5,1\le \sum _{i=1}^T{n}_i\le 2\times 10^5,0\le X_i<2^{20}$ 。

蓝桥杯 2021 第一轮省赛 A 组 G 题。

思路

• 我一开始是真的没太看懂题目意思，以为是用动态规划写
• 别人的思路

题解

#include
using namespace std;
const int M=21;
int T,n,cnt[M];
int main(){
	scanf("%d",&T);
	while(T--){		
		memset(cnt,0,sizeof cnt);
		scanf("%d",&n);
		int sum=0;
		for(int i=1;i<=n;i++){
			int x;
			scanf("%d",&x);
			sum^=x;
			for(int j=0;j<M;j++)	cnt[j]+=(x>>j)&1;
		}
		if(!sum)	puts("0");
		else{
			for(int i=20;i>=0;i--){
				if(!(cnt[i]&1))	continue;
				else if(cnt[i]==1)	puts("1");
				else if((n-cnt[i])&1)	puts("-1");
				else puts("1");
				break;
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

总结

1. 贪心往往都是细分到每一步都需要进行贪心，从这个思路着手（protecting the flower，每一步 —— 对相邻两个数据进行比较）（矩阵消除游戏，每一步 —— 枚举每一种选择的可能，进行最大值比较）（兔子的区间密码，起床困难综合症，每一步 —— 二进制上获取最多的1）
2. 所做的贪心算法不能对后面的贪心选择有影响（矩阵消除游戏，我一开始的WA的方法就违反了这个条例）（按位贪心 —— 二进制的每一位对其他位都没有影响）