我的算法修炼之路--9——重要算法思想：贪心、二分、正难则反、多重与完全背包精练
💗博主介绍：计算机专业的一枚大学生 来自重庆 @燃于AC之乐✌专注于C++技术栈，算法，竞赛领域，技术学习和项目实战✌💗
💗根据博主的学习进度更新（可能不及时）
💗后续更新主要内容：C语言，数据结构，C++、linux（系统编程和网络编程）、MySQL、Redis、QT、Python、Git、爬虫、数据可视化、小程序、AI大模型接入，C++实战项目与学习分享。
👇🏻 精彩专栏 推荐订阅👇🏻
点击进入🌌作者专栏🌌：
Linux系统编程✅
算法画解 ✅
C++ ✅
🌟算法相关题目点击即可进入实操🌟
感兴趣的可以先收藏起来，请多多支持，还有大家有相关问题都可以给我留言咨询，希望希望共同交流心得，一起进步，你我陪伴，学习路上不孤单！
文章目录
前言
这些题目摘录于洛谷，好题，典型的题，考察各类算法运用，可用于蓝桥杯及各类算法比赛备战，算法题目练习，提高算法能力，补充知识，提升思维。
锻炼解题思路，从学会算法模板后，会分析，用到具体的题目上。
对应题目点链接即可做。
本期涉及算法：贪心 + 动态规划（多重背包），差分，贪心，二分答案，正难则反 + 贪心，完全背包（动态规划）。
题目清单
1.Space Elevator 太空电梯
题目：P6771 [USACO05MAR] Space Elevator 太空电梯
解法：贪心 + 动态规划（多重背包）
贪心： 当我们从前往后考虑每⼀个方块的时候，限定高度a[i]小的应该优先考虑。因为如果先放限定高度大的，这些限定高度小的就没法放了。因此，先对所有的方块按照限定高度a[i]从小到大排序。
接下来的问题就是挑⼀些方块出来，在不超过每⼀种方块的限定⾼度下，看看能堆成的最大高度是多
少。正好是多重背包问题。
1.状态表示：
f[i] [j]表示：从前 i 个方块中挑选，总⾼度不超过 j 的情况下，最大的高度是多少。
结果： 整个f表中的最大值，就是我们要的结果。这里要注意，并不是 f[n] [m]，因为有可能考
虑不到第n个方块根本考虑不进去，最后一行根本就不会更新。
2.状态转移方程：
根据第i个方块选的数量，可以分成c[i] + 1种情况，要的是所有情况的最大值。设选了k个
方块，那么最大高度为f[i - 1] [j - k * h[i]] + k * h[i] 。
注意限定条件，循环⾼度的时候不能超过a[i] ，并且j - k * h >= 0 。
3.初始化：
取max,全部初始化为0。
4.填表顺序：
从左到右，空间优化（第二层循环：（逆序）从大到小）
代码：
#include<iostream>#include<algorithm>usingnamespace std;constint N =410, M =4e4+10;int n;structnode{int h, a, c;}e[N];//int f[N][M]; 优化一维int f[M];boolcmp(node& x, node& y){return x.a < y.a;}intmain(){ cin >> n;for(int i =1; i <= n; i++) cin >> e[i].h >> e[i].a >> e[i].c;sort(e +1, e +1+ n, cmp);int ret =0;//多重背包 for(int i =1; i <= n; i++){int h = e[i].h, a = e[i].a, c = e[i].c;for(int j = a; j >=0; j--)//第二层循环逆序{for(int k =0; k <= c && k * h <= j; k++){ f[j]=max(f[j], f[j - k * h]+ k * h);} ret =max(ret, f[j]);}} cout << ret << endl;return0;}2.语文成绩
题目：P2367 语文成绩
解法：差分
这道题就是一道差分的模板题目，不断维护（+ -）区间内的所有内容（学生成绩），然后用前缀和还原数组，一边还原，一边求最小值。
代码：
#include<iostream>usingnamespace std;constint N =5e6+10;int n, p;int f[N];intmain(){ cin >> n >> p;for(int i =1; i <= n; i++)//差分数组 {int x; cin >> x; f[i]+= x; f[i +1]-= x;}while(p--)//维护差分数组 {int x, y,z; cin >> x >> y >> z; f[x]+= z; f[y +1]-= z;}int ret =1e9;for(int i =1; i <= n; i++)//前缀和还原数组 { f[i]+= f[i -1]; ret =min(ret, f[i]);} cout << ret << endl;return0;}3.跳跳
题目：P4995 跳跳！
解法：贪心
先从小到大进行排序，每次都跳距离当前位置最远的位置（h差最大），左右跳，用双指针（下标）更新。
代码：
#include<iostream>#include<algorithm>usingnamespace std;typedeflonglong LL;constint N =310;int n; LL h[N];intmain(){ cin >> n;for(int i =1; i <= n; i++) cin >> h[i];sort(h +1, h +1+ n);int l =0, r = n; LL sum =0;while(l < r){ sum +=(h[l]- h[r])*(h[l]- h[r]); l++; sum +=(h[l]- h[r])*(h[l]- h[r]); r--;} cout << sum << endl;return0;}4.数列分段 Section II
解法：二分答案
看到题目的关键词“最大值最小”，立马想到二分算法，并且也可以写出二段性：
当分的段数越多的时候，最大的和越小；
当分的段数越少的时候，最大的和越小。
因此，可以用二分答案来解决。
关于（计算） calc 函数，传入⼀个和 x，求出最少能分多少段：
从前往后累加，只要和小于 x，就⼀直加；（这里用long long，防溢出）
直到和超过 x，之前的为⼀段，然后从该位置继续累加。注意：最后要额外加一段（最后一段）。
代码：
#include<iostream>usingnamespace std;typedeflonglong LL;constint N =1e5+10;int n, m; LL a[N];intcalc(LL x){int cnt =0, sum =0;for(int i =1; i <= n; i++){ sum += a[i];if(sum > x){ cnt++; sum = a[i];}}return cnt +1;//划分后，最后还有一段 }intmain(){ cin >> n >> m; LL l =0, r =0;for(int i =1; i <= n; i++){ cin >> a[i]; l =max(l, a[i]); r += a[i];}while(l < r){ LL mid =(l + r)/2;if(calc(mid)<= m) r = mid;else l = mid +1;} cout << l << endl;return0;}5.修理牛棚
题目：P1209 [USACO1.3] 修理牛棚 Barn Repair
解法：正难则反 + 贪心
这道题既要求了木板数有限，有要求了木板长度最短，如果挨个考虑放置每个木板的话，非常复杂，用dfs暴搜会超时。那么，我们将问题转化（逆向思维）：先放一块长木板，考虑中间的间隔，m个木板，就有m - 1个间隔，（c头奶牛，最多间隔数c - 1）。用贪心：排序，优先考虑处理间隔较长的，这样用的木板总长度最短。 模板长度：a[c] - a[1] + 1。
代码：
#include<iostream>#include<algorithm>usingnamespace std;constint N =210;int m, s, c;int a[N];//奶牛所占牛棚编号 int b[N];//间隔 boolcmp(int a,int b){return a > b;}intmain(){ cin >> m >> s >> c;for(int i =1; i <= c; i++) cin >> a[i];sort(a +1, a +1+ c);for(int i =1; i < c; i++){ b[i]= a[i +1]- a[i]-1;}sort(b +1, b +1+ c, cmp);int ret = a[c]- a[1]+1;for(int i =1; i < m && i < c; i++){ ret -= b[i];} cout << ret << endl;return0;}6.货币系统
解法：完全背包（动态规划）
由题目“无穷多张”，可以想到用完全背包解题。
题意：就是在一堆数中选几个数能够表示其他所有的数（货币表示问题），选出最少的数组个数。
性质：1.由于较大的数只能较小的数（<=）表示，那么可以先对所有的数升序排序；2.如果一个数i能被[i, i - 1]区间内的数表示，就可以舍去，如果不能，就保留。
于是，先排序，这道题目就转化为完全背包问题：
1.状态表式： bool f[i] [j]从前i个纸币挑选，能否凑成总和为j;
2.**状态转移方程：**f[i] [j] ：1.不选，f[i - 1] [j]; 2.选， f[i] [j - a[i]] 用||(二者满足其一即可)；
3.**初始化：**f[0] [0] = true，方便用于后面更新正确；
4.**填表顺序：**第二层（for循环），完全背包，从小到大；
5.**结果确定：**因为更新到这个数i之后，i一定能被本身表示，所以后面i一定会变为true，一边循环，一边更新结果（在第二层开始之前，第一层），如果f[a[i]] == 0, 就是还不能被表示出来，结果+1。
多组数据测试，每次要清空。
代码：
#include<iostream>#include<algorithm>#include<cstring>usingnamespace std;constint N =110, M =25010;int n;int a[N];bool f[M];intmain(){int T; cin >> T;while(T--){ cin >> n;for(int i =1; i <= n; i++) cin >> a[i];sort(a +1, a +1+ n);memset(f,0,sizeof f);//清空数据 f[0]=true;int ret =0;for(int i =1; i <= n; i++){if(!f[a[i]]) ret++;//1~i-1不能凑出i,保留ifor(int j = a[i]; j <= a[n]; j++){ f[j]= f[j]|| f[j - a[i]];//用||一个满足即可 }} cout << ret << endl;}return0;}加油！志同道合的人会看到同一片风景。
看到这里请点个赞，关注，如果觉得有用就收藏一下吧。后续还会持续更新的。 创作不易，还请多多支持！
