我的算法修炼之路--9——重要算法思想：贪心、二分、正难则反、多重与完全背包精练

Ne0inhk

15 Mar 2026 — 10 min read

💗博主介绍：计算机专业的一枚大学生来自重庆 @燃于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

题目：P1182 数列分段 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.货币系统

题目：P5020 [NOIP 2018 提高组] 货币系统

解法：完全背包（动态规划）

由题目“无穷多张”，可以想到用完全背包解题。

题意：就是在一堆数中选几个数能够表示其他所有的数（货币表示问题），选出最少的数组个数。

性质：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;}