目录

Acwing算法基础课第六讲总结

本讲主要内容
贪心算法。

区间问题

AcWing-905 区间选点

原题链接

思路
参考代码
#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 100010;
struct Range
{
    int l, r;
}ranges[maxn];

bool cmp(Range a, Range b)
{
    return a.r < b.r;
}

int main(void)
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        ranges[i] = {a, b};
    }

    int res = 0, ed = -2e9;
    sort(ranges, ranges + n, cmp);
    for(int i = 0; i < n; i++)
    {
        if(ranges[i].l > ed)
        {
            res++;
            ed = ranges[i].r;
        }
    }
    printf("%d\n", res);

    return 0;
}

AcWing-908 最大不相交区间数量

原题链接

思路
参考代码
#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 100010;
struct Range
{
    int l, r;
}ranges[maxn];

bool cmp(Range a, Range b)
{
    return a.r < b.r;
}

int main(void)
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        ranges[i] = {a, b};
    }

    sort(ranges, ranges + n, cmp);
    int res = 0, ed = -2e9;
    for(int i = 0; i < n; i++)
    {
        if(ranges[i].l > ed)
        {
            res++;
            ed = ranges[i].r;
        }
    }
    printf("%d\n", res);

    return 0;
}

AcWing-906 区间分组

原题链接

思路
参考代码
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;

const int maxn = 100010;
struct Range
{
    int l, r;
}ranges[maxn];

bool cmp(Range a, Range b)
{
    return a.l < b.l;
}

int main(void)
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        ranges[i] = {a, b};
    }

    sort(ranges, ranges + n, cmp);
    priority_queue<int, vector<int>, greater<int>> heap;
    for(int i = 0; i < n; i++)
    {
        auto rg = ranges[i];
        if(heap.empty() || heap.top() >= rg.l)
            heap.push(rg.r);
        else 
        {
            heap.pop();
            heap.push(rg.r);
        }
    }

    int t = heap.size();
    printf("%d\n", t);

    return 0;
}

AcWing-907 区间覆盖

原题链接

思路
参考代码

Huffman树

AcWing-148 合并果子

原题链接

思路
参考代码

排序不等式

AcWing-913 排队打水

原题链接

思路
参考代码

绝对值不等式

AcWing-104 货仓选址

原题链接

思路
参考代码

推公式

AcWing-125 耍杂技的牛

原题链接

思路
参考代码