算法题目优选（蓝桥杯备战）--2
💗博主介绍：计算机专业的一枚大学生 来自重庆 @燃于AC之乐✌专注于C++技术栈，算法，竞赛领域，技术学习和项目实战✌💗
💗根据博主的学习进度更新（可能不及时）
💗后续更新主要内容：C语言，数据结构，C++、linux（系统编程和网络编程）、MySQL、Redis、QT、Python、Git、爬虫、数据可视化、小程序、AI大模型接入，C++实战项目与学习分享。
👇🏻 精彩专栏 推荐订阅👇🏻
点击进入🌌作者专栏🌌：
算法画解 ✅
C++ ✅
🌟算法相关题目点击即可进入实操🌟
感兴趣的可以先收藏起来，请多多支持，还有大家有相关问题都可以给我留言咨询，希望希望共同交流心得，一起进步，你我陪伴，学习路上不孤单！
文章目录
前言
这些题目摘录于洛谷，好题，典型的题，考察各类算法运用，可用于蓝桥杯及各类算法比赛备战，算法题目练习，提高算法能力，补充知识，提升思维。
锻炼解题思路，从学会算法模板后，会分析，用到具体的题目上。
分享
试想一下多年以后，你真的成为自己最喜欢的样子，那么此刻如果身处低谷，你真的不再为自己努力尝试一下吗？每个人的起点不同，不要为此感到愤恨不公，把握有限的时间，让自己变的更好，用更扎实的学识拖住你的犹豫，用更坚毅的品质挡住你的迷茫。当一切实现，你也许会觉得努力不是独自的成长，也不是突然的蜕变，而是你面对理想的自己，日复一日的靠近。
题目清单
1.奶牛晒衣服
题目：P1843 奶牛晒衣服
解法：二分答案
首先大概率会想到贪心算法，就是优先选择湿度最大的衣服进行烘干，然后选择次之，但是这样的贪心策略是错误的，可以举出反例：
w = [10, 8], a = 1, b = 1; 如果选10， 算出来时间是7s, 但最优解是用烘干机烘干：10 选择烘干4s, 8烘干1s， 结果是6是。
为什么会错？ 因为把自然干看成为每个都有烘干能力为a/s的烘干机，而这种贪心策略在最后浪费了其它烘干机在的烘干湿度。所以最好让最后衣服一起可以烘干。
可以发现烘干机在中途要不断改变烘干的衣服。 这种是很难直接找的。
枚举答案：
设经过的时间是 x 。根据题意，我们可以发现如下性质：
经过的时间如果是 x 的话，烘干机的「使⽤次数」最多也是 x ；
x 与能弄干的衣服在呈正相关；
那么在整个解空间里面，设弄干所有衣服的最少时间是 ret ，于是有：
当 x ≥ ret 时，我们能弄干所有衣服； 满足要求（合法）
当 x < ret 时，我们不能弄干所有衣服。在解空间中，根据ret 的位置，可以将解集分成两部分，具有「⼆段性」，那么我们就可以⼆分答案。不满足要求（不合法）
接下来的重点就是，给定⼀个时间 x，判断「是否能把所有的衣服全部弄干」。当时间为 x时，所
有衣服能够自然蒸发a * x的湿度，于是：
如果 w[i] ≤ a ⋅ x ：让它自然蒸发；
如果 ：需要⽤烘⼲机烘干的湿度，次数为
w[i] > a ⋅ x t = w[i] − a ⋅ x + t / b + (t % b == 0 ? 0 : 1) //优先级：算术 > 逻辑
那么我们可以遍历所有的衣服，计算烘干机的「使用次数」与 x进行判断。
如果使用次数「大于」给定的时间 x ，说明不能全部弄干；
如果使用次数「小于等于」给定的时间 x ，说明能全部弄干。
注意：虽然这里int也能全部通过，这里数据范围是到 5e5 ,但是拿不准还是开long long。
代码：
#include<iostream>usingnamespace std;constint N =5e5+10;typedeflonglong LL; LL n, a, b; LL w[N];//判断boolcheck(LL x){ int cnt =0;for(int i =1; i <= n; i++){ if(w[i]<= a * x)continue;int d = w[i]- a * x; cnt += d / b +(d % b ==0?0:1);}return cnt <= x;}intmain(){ cin >> n >> a >> b;for(int i =1; i <= n; i++) cin >> w[i];//二分答案 LL l =1, r =5e5;while(l < r){ LL mid =(l + r)/2;if(check(mid)) r = mid;else l = mid +1;} cout << l << endl;return0;}2.砝码称重
解法：多重背包
求得是可以凑出得重量种数，首先想到暴力枚举，排列组合等方法，但难以找到枚举或排列的方法，且时间复杂度大，过于复杂。
重量： w:[1, 2, 3, 5, 10, 20]
数量： a[] :[a1, a2, a3, a4, a5, a6]
思路转化： 设选的 w总 = j,这道题就转化为从前i种物品中选物品，总重量为j的所有选法。 这样题目就转化为多重背包问题（物品个数有限制）。
执行多重背包的逻辑：
1.状态表式：
表示：从前 i 种砝码中挑选，是否能凑成总质量为 j 。
最终结果就是 f 表里面最后⼀⾏为 true 的个数。f[n] [j]里面找， f[n] [0] 不算。
2.状态转移⽅程：
根据第 i 个砝码选的个数，能分成 a[i] + 1 种情况，设选了0,1, …… k 个。
此时重量为 w[i] × k ，那么就应该去前⾯看看能不能凑成 j − w[i] × k ，即：f[i - 1] [j - w[i] * k]
在所有的情况里面，只要有⼀个为真， f[i] [j] 就为真。
3.初始化：
f[0] [0] = 1，起始状态，也是为了后续填表有意义且正确。
4.填表顺序：
从上往下每一行，每一行从左往右。
数据范围， 可知 j <= 1000,用于循环更新所有，选的情况。
细节： 优化一维，第二层for要逆序处理， 0 <= k <= a[i], k * w[i] <= j.
代码：
#include<iostream>usingnamespace std;constint N =1010;int w[]={ 0,1,2,3,5,10,20};int a[10];int f[N];//f[i][j]从前i个物品中挑选，能否凑出重量为j intmain(){ for(int i =1; i <=6; i++) cin >> a[i];//初始化 f[0]=1;//多重背包for(int i =1; i <=6; i++){ for(int j =1000; j >=0; j--)//优化一维，逆序处理 { for(int k =0; k <= a[i]&& k * w[i]<= j; k++){ f[j]= f[j]|| f[
