当前位置：首页 > news >正文

算法·贪心

news 2026/7/31 10:36:30

文章目录

贪心
- 基本原理
- 适用条件
个人总结
- 局部最优到全局最优
贪心应用
- 区间拆分和合并问题：
- - 区间合并问题
  - 区间重叠问题
  - 其他区间问题
  - 隐式的区间贪心
- 哈夫曼树
- 搭积木模型
- - 基本思路
- 接雨水问题
例题
- 其他练习题

贪心

基本原理

核心：局部最优到全局最优
贪心策略：使用贪心时采取的策略

适用条件

异常广泛，不需要特别注意

个人总结

贪心的精髓在于贪心策略的选取,目前已有明显的贪心策略包含：

局部最优到全局最优

这里蕴含着"递进"的关系，某一范围内满足题意，不断扩大范围，直到覆盖所有范围。
个人感觉这是贪心的最原始的理解。
U535982 J-A 小梦的AB交换:这题需要注意到两个重要事实，事实1：结果只有ABAB…和BABA…两种情况。事实2：考虑A替换的次数(B替换的次数一定与A替换的次数相等)。
小苯的Z串匹配：类同。

贪心应用

区间拆分和合并问题：

排序:不是两侧都可以的
注意边界的更新：交集取最小边界，并集取最大边界
凌乱的yyy / 线段覆盖：区间拆分问题，可以排序左端点，可以排序右端点，主要利用单调性。

区间合并问题

区间合并
所有的区间合并在一起，右端点保证最大，right=max(right,v[i].second)，同时确保v[i].first<=right即可。

区间重叠问题

区间选点：right=min(right,v[i].second)，确保多个区间始终共享重叠部分。

其他区间问题

908. 最大不相交区间数量：选择区间问题，和之前区间中选一个最容易的(right最小的区间)来保证不相交即可，然后right更新回当前区间右端点即可。

voidsolve(){cin>>n;for(inti=1;i<=n;i++){inta,b;cin>>a>>b;v.push_back({a,b});}sort(v.begin(),v.end(),[&](constpr&a,constpr&b){returna.first<b.first;});intcnt=0,right=v[0].second;for(inti=1;i<v.size();i++){// 拆分区间选最小if(v[i].first>right){cnt++;right=v[i].second;}else{right=min(right,v[i].second);}}cnt++;cout<<cnt;}

907. 区间覆盖：贪心思想很直接，尽可能长的区间覆盖，然后动态更新需要保证覆盖的起始点st，确保区间内每一段内容都被覆盖。

voidsolve(){cin>>st>>ed;cin>>n;for(inti=1;i<=n;i++){inta,b;cin>>a>>b;v.push_back({a,b});}sort(v.begin(),v.end(),[&](constpr&a,constpr&b){returna.first<b.first;});intres=0,j=0;while(j<v.size()){intright=INT_MIN;while(j<v.size()&&v[j].first<=st){right=max(v[j].second,right);j++;}if(right==INT_MIN){cout<<-1;return;}res++;st=right;if(right>=ed){cout<<res;return;}}cout<<-1;}

906. 区间分组：和之前的区间的右端点进行考虑，如果满足分组条件更新当前组的右端点。如果最小的右端点都不能满足条件则必须开辟新的组。

需要使用优先级队列来模拟动态更新的情况。

voidsolve(){cin>>n;for(inti=1;i<=n;i++){inta,b;cin>>a>>b;v.push_back({a,b});}sort(v.begin(),v.end(),[&](constpr&a,constpr&b){returna.first<b.first;});//cout << endl;//for (auto item : v) {// cout << item.first << " " << item.second << endl;//}intcnt=0;for(inti=0;i<v.size();i++){if(q.size()){if(v[i].first<=q.top()){cnt++;}else{q.pop();}}q.push(v[i].second);}cnt++;cout<<cnt;}

隐式的区间贪心

哈夫曼树

[NOIP2004 提高组] 合并果子：哈夫曼树问题

搭积木模型

单调递增：这里的递增是从最低点开始(也就相当于假设路面铺平)，需要额外填充
单调递减：很容易想到不需要额外填充
P1969 [NOIP 2013 提高组] 积木大赛：搭积木问题
P5019 [NOIP 2018 提高组] 铺设道路：搭积木问题
122.买卖股票的最佳时机II：

基本思路

将数组几何化，本质上等价于堆积木，如果ai-1<ai，则在堆ai时顺便也完成了ai-1的工作
例如堆第4列时已经完成了第3列的工作，只需要额外完成第4列多出来的工作，所以有ai-ai-1
以下图例不是我的，引自大佬
ans+vec[1]是因为默认先搭建第一列，剩下所有的积木都是相对于第一列搭建的

#include<bits/stdc++.h>using namespace std;using ll=long long;int n;ll ans=0;vector<ll>vec(100009,0);voidsolve(){cin>>n;for(inti=1;i<=n;i++){cin>>vec[i];}for(inti=2;i<=n;i++){if(vec[i]>vec[i-1]){ans+=vec[i]-vec[i-1];}}cout<<ans+vec[1];}signedmain(){std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);solve();return0;}