【算法/训练】：贪心（算法 & 题目训练）
【算法/训练】：贪心（算法 & 题目训练）
前言 🚀
基本概念
在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
特性
贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。
- 能够用贪心算法求解的问题一般具有两个重要特性：贪心选择性质和最优子结构性质
1. 贪心选择性质
- 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素。贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题
- 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。
- 证明的大致过程为：
- 首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。
- 做了贪心选择后，原问题简化为规模更小的类似子问题。
- 然后用数学归纳法证明通过每一步做贪心选择，最终可得到问题的整体最优解。
- 其中，证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质
2. 最优子结构性质
- 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。
3. 贪心算法与动态规划算法的差异
- 动态规划和贪心算法都是一种递推算法，均有最优子结构性质，通过局部最优解来推导全局最优解。
- 两者之间的区别在于：
- 贪心算法中作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一步之前的最优解则不作保留，贪心算法每一步的最优解一定包含上一步的最优解。
- 动态规划算法中全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解。
具体例题如下 📚
1. 买卖股票的最好时机(二)
思路： 只要当天价格比上一天价格大，就累加，示意图如下，然后算出最大利润即可
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int maxProfit(vector<int>& prices) {
// write code here
int ret = 0;
for (int i = 0; i < prices.size(); i++)
{
if (prices[i] > prices[i - 1]) ret += prices[i] - prices[i - 1];
}
return ret;
}
int main()
{
int n;
cin >> n;
vector<int> prices;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
prices.emplace_back(x);
}
cout << maxProfit(prices) << endl;
return 0;
}2. 拼数
解析： 先把整数化成字符串，然后再比较a+b和b+a，如果a+b>b+a，就把a排在b的前面，反之则把a排在b的后面，最后输出排序后的字符串，即可得到最大的整数（如果求最小的整数，则从小到大排序）。 举例说明：a=‘123’，b=‘71’，a+b='12371'，b+a=‘71123’，所以a+b<b+a，将b排在前面 注意：正常的字符串存在比较缺陷，如：A=’321’，B=’32’，按照标准的字符串比较规则因为A>B，所以A+B > B+A ，而实际上’32132’ < ’32321’。 具体步骤如下： 1.获取n 2.依次获取n个正整数，将整数转换为字符串：声明字符串数组a[n]，将获取到的正整数存入数组a中，即可实现正整数到字符串的转换 3.自定义排序函数：如果a+b>b+a，则把a排在前面，否则将b排在前面（对于字符串a、b，a+b表示连接两个字符串形成一个新串） 4.从大到小输出排序后的字符串即可得到最大的整数
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
bool cmp(string s1, string s2){
return s1 > s2;
}
int main(){
int n;
cin >> n;
vector<string> s;
for (int i = 0; i < n; i++){
string ch;
cin >> ch;
s.push_back(ch);
}
sort(s.begin(), s.end());
for (auto e : s) cout << e;
return 0;
}3. 组队竞赛
思路： 排序+贪心。每次选择当前剩余的人之中，水平最高的两个人和水平最低的一个人组队，这样就能最大化团队水平中位数的值。
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
// ———— 乒乓球筐
void solve1()
{
string s, t;
while (cin >> s >> t)
{
map<char, int> mp;
for (auto e : s)
{
mp[e]++;
}
for (auto e : t)
{
mp[e]--;
}
int f = 1;
for (auto e : mp)
{
if (e.second < 0) f = 0;
}
if (f == 0) cout << "No" << endl;
else cout << "Yes" << endl;
}
}
const int N = 300010;
int a[N];
void solve2()
{
int n;
cin >> n;
for (int i = 0; i < 3 * n; i++) {
cin >> a[i];
}
sort(a, a + 3 * n);
long long ans = 0;
int r = 3 * n - 1, l = 0;
while (l < n)
{
ans += a[r - 1];
r -= 2;
l++;
}
cout << ans << "\n";
}
int main()
{
solve2();
}4. 拼数
思路： 先把整数化成字符串，然后再比较a+b和b+a，如果a+b>b+a，就把a排在b的前面，反之则把a排在b的后面，最后输出排序后的字符串，即可得到最大的整数（如果求最小的整数，则从小到大排序）。 举例说明：a=‘123’，b=‘71’，a+b='12371'，b+a=‘71123’，所以a+b<b+a，将b排在前面 注意：正常的字符串存在比较缺陷，如：A=’321’，B=’32’，按照标准的字符串比较规则因为A>B，所以A+B > B+A ，而实际上’32132’ < ’32321’。 具体步骤如下： 1.获取n 2.依次获取n个正整数，将整数转换为字符串：声明字符串数组a[n]，将获取到的正整数存入数组a中，即可实现正整数到字符串的转换 3.自定义排序函数：如果a+b>b+a，则把a排在前面，否则将b排在前面（对于字符串a、b，a+b表示连接两个字符串形成一个新串） 4.从大到小输出排序后的字符串即可得到最大的整数
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(string a, string b) {
return a + b > b + a;
}
int main() {
int n;
cin >> n;
vector<string> ans(n);
for (int i = 0; i < n; i++)
cin >> ans[i];
sort(ans.begin(), ans.end(), cmp);
for (auto e : ans) cout << e;
return 0;
}5. 华华听月月唱歌
思路： 该题的贪心策略就是每次向后寻找能跳到的区间里面右端最远的那一个，如果挑不到或者最后不足N那么就证明无法满足，因此我们可以定义一个cmp函数来进行排序。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct node {
int l, r; //左右区间
};
bool cmp(node a,node b) {
if (a.l != b.l) return a.l < b.l;
return a.r > b.r;
}
int main(){
int n, m;
cin >> n >> m;
vector<node> ans(m);
for (int i = 0; i < m; i++)
cin >> ans[i].l >> ans[i].r;
sort(ans.begin(), ans.end(), cmp);
if (ans[0].l != 1) {//如果最左边节点不是1的话，就做不到
cout << -1 << endl;
return 0;
}
int ret = 1; //记录最少选择区间
int maxr = ans[0].r, tmp = ans[0].r; //记录最大右边
for (int i = 1; i < m && maxr < n;) {
while (i < m && ans[i].l <= maxr + 1) { //记住是 + 1,因为 [1,3] 和[4, 5]可以直接相连
tmp = max(tmp, ans[i].r); //记录在当前最大的右边的时候，可以进来多少个左边
i++;
}
if (tmp == maxr) break;
ret++;
maxr = tmp;
}
if (maxr >= n) //当最大右边大于等于n时即可
cout << ret << endl;
else cout << -1 << endl;
return 0;
}6. 非对称之美
思路： 这题我们的主要思路是用贪心，
- 先判断整个字符串是否是回文，那么就从后面往前走，逐渐-1
- 还有个特殊情况，字符串中字符全都相同的时候，就直接返回0
- 易知可输出答案只有0，n，n - 1
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void solve3() {
string s;
cin >> s;
int n = s.size();
// 1. 判断是否全部相同
bool f = false; //判断是否是回文
for (int i = 1; i < n; i++) {
if (s[i] != s[0]) {
f = true;
break;
}
}
if (f == false){
cout << 0 << endl;
return;
}
// 2. 不是相同字符
f = false;
// 3. 判断本身是否为回文
int l = 0, r = n - 1;
while (l < r) {
if (s[l] == s[r]) l++, r--;
else {
f = true; //本身不是回文
break;
}
}
if (f) cout << n << endl;
else cout << n - 1 << endl;
}
int main()
{
solve3();
return 0;
}7. 主持人调度（二）
//方法一：差分数组的映射
int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
map<int, int> mp;
for (int i = 0; i < startEnd.size(); i++) {
mp[startEnd[i][0]]++; //左边 ++
mp[startEnd[i][1]]--; //右边 --
}
int ans = 0, res = 0;
for (auto ip : mp) {
res += ip.second;
ans = max(ans, res);
}
return ans;
}
//方法二：小根堆，只进入右端点，进入点的左端点和堆顶作比较
int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
sort(startEnd.begin(), startEnd.end(), [&](vector<int> a, vector<int>b)->bool
{
return a[0] < b[0];
});
priority_queue<int,vector<int>,greater<int>> heap;
heap.push(startEnd[0][1]);//入右端点
for (int i = 1; i < n; i++) {
int a = startEnd[i][0], b = startEnd[i][1];
if (a >= heap.top()) //无重叠
{
heap.pop();
heap.push(b);
}
else heap.push(b); //有重叠
}
return heap.size();
}8. 活动安排
思路：
- 先进行排序，然后如果两个活动出现了交集，就选择右端点较小的那个活动。
后续：
后面会持续更新关于贪心的题目来这里，敬请期待啦💞 💞
腾讯云开发者
