算法·贪心

文章目录贪心基本原理适用条件个人总结局部最优到全局最优贪心应用区间拆分和合并问题区间合并问题区间重叠问题其他区间问题隐式的区间贪心哈夫曼树搭积木模型基本思路接雨水问题例题其他练习题贪心基本原理核心局部最优到全局最优贪心策略使用贪心时采取的策略适用条件异常广泛不需要特别注意个人总结贪心的精髓在于贪心策略的选取,目前已有明显的贪心策略包含局部最优到全局最优这里蕴含着递进的关系某一范围内满足题意不断扩大范围直到覆盖所有范围。个人感觉这是贪心的最原始的理解。U535982 J-A 小梦的AB交换:这题需要注意到两个重要事实事实1结果只有ABAB…和BABA…两种情况。事实2考虑A替换的次数(B替换的次数一定与A替换的次数相等)。小苯的Z串匹配类同。贪心应用区间拆分和合并问题排序:不是两侧都可以的注意边界的更新交集取最小边界并集取最大边界凌乱的yyy / 线段覆盖区间拆分问题可以排序左端点可以排序右端点主要利用单调性。区间合并问题区间合并所有的区间合并在一起右端点保证最大rightmax(right,v[i].second)同时确保v[i].firstright即可。区间重叠问题区间选点rightmin(right,v[i].second)确保多个区间始终共享重叠部分。其他区间问题908. 最大不相交区间数量选择区间问题和之前区间中选一个最容易的(right最小的区间)来保证不相交即可然后right更新回当前区间右端点即可。voidsolve(){cinn;for(inti1;in;i){inta,b;cinab;v.push_back({a,b});}sort(v.begin(),v.end(),[](constpra,constprb){returna.firstb.first;});intcnt0,rightv[0].second;for(inti1;iv.size();i){// 拆分区间选最小if(v[i].firstright){cnt;rightv[i].second;}else{rightmin(right,v[i].second);}}cnt;coutcnt;}907. 区间覆盖贪心思想很直接尽可能长的区间覆盖然后动态更新需要保证覆盖的起始点st确保区间内每一段内容都被覆盖。voidsolve(){cinsted;cinn;for(inti1;in;i){inta,b;cinab;v.push_back({a,b});}sort(v.begin(),v.end(),[](constpra,constprb){returna.firstb.first;});intres0,j0;while(jv.size()){intrightINT_MIN;while(jv.size()v[j].firstst){rightmax(v[j].second,right);j;}if(rightINT_MIN){cout-1;return;}res;stright;if(righted){coutres;return;}}cout-1;}906. 区间分组和之前的区间的右端点进行考虑如果满足分组条件更新当前组的右端点。如果最小的右端点都不能满足条件则必须开辟新的组。需要使用优先级队列来模拟动态更新的情况。voidsolve(){cinn;for(inti1;in;i){inta,b;cinab;v.push_back({a,b});}sort(v.begin(),v.end(),[](constpra,constprb){returna.firstb.first;});//cout endl;//for (auto item : v) {// cout item.first item.second endl;//}intcnt0;for(inti0;iv.size();i){if(q.size()){if(v[i].firstq.top()){cnt;}else{q.pop();}}q.push(v[i].second);}cnt;coutcnt;}隐式的区间贪心哈夫曼树[NOIP2004 提高组] 合并果子哈夫曼树问题搭积木模型单调递增这里的递增是从最低点开始(也就相当于假设路面铺平)需要额外填充单调递减很容易想到不需要额外填充P1969 [NOIP 2013 提高组] 积木大赛搭积木问题P5019 [NOIP 2018 提高组] 铺设道路搭积木问题122.买卖股票的最佳时机II基本思路将数组几何化本质上等价于堆积木如果ai-1ai则在堆ai时顺便也完成了ai-1的工作例如堆第4列时已经完成了第3列的工作只需要额外完成第4列多出来的工作所以有ai-ai-1以下图例不是我的引自大佬ansvec[1]是因为默认先搭建第一列剩下所有的积木都是相对于第一列搭建的#includebits/stdc.husing namespace std;using lllong long;int n;ll ans0;vectorllvec(100009,0);voidsolve(){cinn;for(inti1;in;i){cinvec[i];}for(inti2;in;i){if(vec[i]vec[i-1]){ansvec[i]-vec[i-1];}}coutansvec[1];}signedmain(){std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);solve();return0;}接雨水问题单调队列问题 / 贪心问题。添加链接描述例题【深基12.例1】部分背包问题这道题不是0-1背包凌乱的yyy / 线段覆盖区间拆分问题可以排序左端点可以排序右端点主要利用单调性。[NOIP2004 提高组] 合并果子哈夫曼树问题P1969 [NOIP 2013 提高组] 积木大赛搭积木问题P5019 [NOIP 2018 提高组] 铺设道路搭积木问题其他练习题P3817 小A的糖果P4995 跳跳