【C++算法基础】#7贪心法在贪什么?有迹可循吗?

发布于 2023-06-11  725 次阅读


贪心法是十分常见的算法之一,一般来说写法简单,但是正确性难以证明,比较感性。

🎈 作者:Eriktse
🎈 简介:211计算机在读,CCPC全国赛金牌,ICPC区域赛银牌退役选手🏆力争以通俗易懂的方式讲解编程和算法!❤️欢迎关注我,一起交流C++/Python算法。(优质好文持续更新中……)🚀
🎈欢迎加群一起玩耍~QQ群:600240150

贪心法的使用前提

1.可以找到一个局部最优解。

2.可以从局部最优解,推广到全局最优解。

在课本上,两个条件分别是:最优子结构和贪心选择性质。

一般来说,贪心法往往是将某个东西排序,或者用堆等数据结构,每一步都取局部最优解,进而得到全局最优解。

关于优先队列(堆)的介绍:https://www.eriktse.com/technology/1075.html

分析步骤

1.确定要贪的东西和贪心策略,或者说根据什么东西来贪心。比如某个物品的性价比,我们优先选性价比高的,或者说某个区间,按照左端点还是右端点进行排序等等。

2.从局部的特殊情况出发,简单分析选择“贪心策略”是不劣的,也就是选择贪心的方法,一定不会比其他方法更差。

一般来说,大多数能够贪心的东西,对答案的贡献都相等。比如背包问题中,如果每件物品体积都相等,那肯定是性价比优先。当有多种选择,但是他们对答案的贡献相等时,我们会选择开销较小的,或者是能够给后面留下更多选择空间的。

3.开始贪心,得到问题的解。

例题

ETOJ 1035: 小e看电视

题目链接:http://oj.eriktse.com/problem.php?id=1035

贪心法,当右端点相等的时候,选任意一个合法的区间都一样,且最多选择一个,所以按照右端点升序排列。特殊情况是,区间大小为$0$,为了算上这个区间,可以在右端点相等时按照左端点升序排列。

然后从左到右遍历这个数组,如果合法就选择即可。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 2e5 + 9, T = 20;

struct Node
{
    int l, r;
}a[N];

void solve()
{
    int n;cin >> n;
    for(int i = 1;i <= n; ++ i)cin >> a[i].l >> a[i].r;

    sort(a + 1, a + 1 + n, [](const Node &u, const Node &v)
    {
        return u.r == v.r ? u.l < v.l : u.r < v.r;
    });

    int now = 1, ans = 0;
    for(int i = 1;i <= n; ++ i)
    {
        if(a[i].l < now)continue;
        now = a[i].r, ans ++;
    }
    cout << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
    while(_ --)solve();
    return 0; 
}

ETOJ 1036: 我踏马吃吃吃吃吃

题目链接:http://oj.eriktse.com/problem.php?id=1036

排队取水问题,典型的贪心,我们按照等候时间从小到大排序,然后每次将等候时间最小的人放入“总时间最少的窗口”即可,这个可以用优先队列来维护。

最终计算出的所有人的等待时间之和最小。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1e6 + 9;

ll a[N];

void solve()
{
    int n, m;cin >> n >> m;
    for(int i = 1;i <= n; ++ i)cin >> a[i];

    sort(a + 1, a + 1 + n);

    priority_queue<ll, vector<ll>, greater<ll>> pq;

    for(int i = 1;i <= m; ++ i)pq.push(0);

    ll ans = 0;
    for(int i = 1;i <= n; ++ i)
    {
        ll x = pq.top();pq.pop();
        pq.push(x + a[i]);
        ans += x;
    }

    cout << ans << '\n';

}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
    while(_ --)solve();
    return 0; 
}