杭州富阳小码王集训营知识梳理
2025-08-01 19:00:36
发布于：浙江
DAY 01 —— 贪心算法
贪心算法的定义
贪心算法（Greedy Algorithm）是一种在每一步决策中都采取当前状态下最优（即最有利）的选择，从而希望导致结果是全局最优的解题策略。它不追求整体最优，而是通过一系列局部最优的选择，逐步构建最终解决方案，最终期望得到全局最优解。
贪心排序
在数据之间没有相互的联系时，可以通过对数组（或其他类型的变量，例如string类型）的排序来取得最优解。
这里顺便复习一下sort()排序。
普通数组：
sort(a,a+n); //此为升序排列，格式sort(数组名+第一个开始要排序的下标,数组名+最后一个要排序的下标+1);
sort(a,a+n,greater<int>); //此为升序排列，格式sort(数组名+第一个开始要排序的下标,数组名+最后一个要排序的下标+1,greater<数组元素的类型>());
其他类型（vector，string）：
sort(s.begin(),s.end());
//这里与普通数组的区别仅仅只有下标的区别
例题
题目描述
在一个神秘的魔法王国里，两个强大的巫师，
吉娜 和 安度因，他们在打一起打副本的时候遇到了一个难题。
现在每个巫师手里都有一个装满魔法符文的袋子，这些符文由小写英文字母分别表示为字符串 s和 t。他们可以通过重新排列各自字符串中的字符来获得一个新的符文组合。
如果两位巫师可以在重新排列字符串 s和 t 后让 s的字典序 < t 的字典序输出YES，否则输出NO。
参考代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int T;
cin >> T;
string t,s;
while(T--){
cin >> s >> t;
sort(s.begin(),s.end());
sort(t.begin(),t.end(),greater<char>());
s >= t ? cout << "NO\n" : cout << "YES\n";
}
return 0;
}
这道题让我们求字符串 和 重新排序后能否让 的字典序小于 的字典序。
所以贪心思想就是将 按字典序按最小的情况排序，将 按字典序最大的情况排序，如果这样都不行的话，那就说明 的字典序绝对大于 的字典序。
贪心 - 优先队列
优先队列是什么？
优先队列是一种特殊队列，元素按优先级排序，出队时优先取出最高优先级元素，常用于调度、任务处理等场景，实现方式有堆、二叉搜索树等。
优先队列分为两种：升序与降序。
//优先队列的创建
priority_queue<int, vector<int>, greater<int>> q;
/*
priority_queue的第三个参数greater<int>指定了比较方式，使用该比较器时，
队列会以升序（从小到大）排列元素，即最小的元素会被优先取出。
*/
priority_queue<int，vector<int>> q;
//priority_queue中只有两个参数，未指定第三个参数，默认为降序（从大到小）。
为什么要使用优先队列
请看这道题：
题目描述
在一个果园里，超级阿拉已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。超级阿拉决定把所有的果子合成一堆。
每一次合并，超级阿拉可以把两堆果子合并到一起（不一定是相邻的两堆果子），消耗的体力等于两堆果子的重量之和。可以看出，所有的果子合并到最后就只剩下一堆了。超级阿拉在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家，所以超级阿拉在合并果子时要尽可能节省体力。你的任务是使超级阿拉消耗的体力最少，并输出这个最小的体力消耗值
数据范围： 。
为什么这道题要用优先队列，问题就出在数据范围。
sort排序在此代码中时间复杂度为O(n² log n)，在会TLE，然而优先队列能在O(1)时间获取到最小（最大）值，用O(log n)的时间完成插入和删除。
反悔贪心
请看题目：
题目链接
这道题第一反应是前面先用砖块搭上去，后面再用梯子。
但如果你先用了砖头，用完了后遇到了更小的差值，不就反悔了吗？
先用了梯子，用完了后又遇到了更大的差值，不就又反悔了吗？
这道题就是典型的反悔贪心。
#include<bits/stdc++.h>
using namespace std;
int ans;
int main(){
int n,bricks,ladders;
cin >> n;
int a[1145141];
for(int i=0;i<n;i++){
cin >> a[i];
}
cin >> bricks >> ladders;
priority_queue<int,vector<int>,greater<int>>q;
int sum=0;
int ans=n-1;
for(int i=1;i<n;i++){
int H = a[i]-a[i-1];
if(H>0){
q.push(H);
if(q.size() > ladders){
sum+=q.top();
q.pop();
}
}
if(sum>bricks){
ans = i-1;
break;
}
}
cout << ans;
}
前面我们先无脑用梯子，后面遇到差值比较此次差值与前面的差值的最小值用砖头填充就好了。
有帮助，赞一个