五：贪心

贪心问题也没有代码模板。

一条竞赛经验：先暴力求解拿部分分数，然后想正解和暴力对拍。

贪心：一般指每一步取局部最优解，就可以取到全局最优解的问题。

贪心题一般做法：想一个思路，跑几个样例验证一下，然后提交。

5.1：区间问题

区间问题的贪心一般都是上来先按左端点或者右端点排序。

例题：905. 区间选点（模板题）

给定 N 个闭区间 [ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。
输出选择的点的最小数量。
位于区间端点上的点也算作区间内。

输入格式
第一行包含整数 N，表示区间数。
接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。

输出格式
输出一个整数，表示所需的点的最小数量。

数据范围
1≤N≤10^5,
−10^9≤ai≤bi≤10^9
输入样例：
3
-1 1
2 4
3 5
输出样例：
2

本题是区间选点模板题，类似蓝桥杯（二三）中的acwing.112. 雷达设备。

贪心思路：

将每个区间按右端点从小到大排序；
从前往后依次枚举每个区间：
2.1. 如果当前区间包含最后一个（上一个）选择的点，则直接跳过；
2.2. 如果当前区间不包含最后一个选择的点，则在当前区间的右端点的位置选一个新的点；

图示：

贪心证明：

代码：

#include <iostream>
#include  <algorithm>
using namespace std;
#define IOS \
    ios::sync_with_stdio(false); \
    cin.tie(0); \
    cout.tie(0)
const int N = 1e5+ 5;

struct Range{
    int l,r;
    bool operator < (const Range &R) const{
        return r < R.r;
    }
}range[N];
int main(){
    IOS;
    int n;
    cin >> n;
    int a,b;
    for (int i = 0;i < n;i ++){
        cin >> a >> b;
        range[i] = {a,b};
    }

    sort(range,range + n);

    int res = 0,edge = -0x3f3f3f3f;// edge表示每次区间选择的点
    for (int i = 0;i < n;i ++){
        if (range[i].l > edge){ // 如果上一次选择的点edge下标在当前区间内
            res ++;
            edge = range[i].r;// 则选择右端点作为新的edge
        }
    }
    cout << res << '\n';
    return 0;
}

其实按左端点排序也可以。用结构体需要重载<排序，也可以用pair排序。

参考题解： https://www.acwing.com/solution/content/10615/。

例题：908. 最大不相交区间数量（模板题）

给定 N 个闭区间 [ai,bi]，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。
输出可选取区间的最大数量。

输入格式
第一行包含整数 N，表示区间数。
接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。

输出格式
输出一个整数，表示可选取区间的最大数量。

数据范围
1≤N≤10^5,
−10^9≤ai≤bi≤10^9
输入样例：
3
-1 1
2 4
3 5
输出样例：
2

和上一题一模一样的思路。

这种贪心策略选择的右端点数量就是最大不相交区间的数量。

代码一模一样就不放了。

例题：906. 区间分组（模板题）

给定 N 个闭区间 [ai,bi]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。
输出最小组数。

输入格式
第一行包含整数 N，表示区间数。
接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。

输出格式
输出一个整数，表示最小组数。

数据范围
1≤N≤10^5,
−10^9≤ai≤bi≤10^9
输入样例：
3
-1 1
2 4
3 5
输出样例：
2

注意：每组内部的区间两两之间（包括端点）没有交集，端点相交也不行。

算法1：非常巧妙的模拟思路。

参考题解： https://www.acwing.com/solution/content/8902/。

大家可以把这个问题想象成活动安排问题。

有若干个活动，第i个活动开始时间和结束时间是[si,fi]，同一个教室安排的活动之间不能交叠，求要安排所有活动，至少需要几个教室？

有时间冲突的活动不能安排在同一间教室，与该问题的限制条件相同，即最小需要的教室个数即为该题答案。

我们可以把所有开始时间和结束时间排序，遇到开始时间就把需要的教室加1，遇到结束时间就把需要的教室减1,在一系列需要的教室个数变化的过程中，峰值就是多同时进行的活动数，也是我们至少需要的教室数。

#include <iostream>
#include  <algorithm>
using namespace std;
#define IOS \
    ios::sync_with_stdio(false); \
    cin.tie(0); \
    cout.tie(0)
const int N = 1e5+ 5;
int b[2*N],idx;

int main(){
    IOS;
    
    int n;
    cin >> n;
    int l,r;
    while (n--){
        cin >> l >> r;
        b[idx++] = 2*l;// 标记左端点为偶数
        b[idx++] = 2*r + 1;// 标记右端点为奇数
    }

    sort(b,b + idx);

    int res = 1,t = 0;// res为至少需要的教室数，t为当前时刻的教室数
    for (int i = 0;i < idx;i ++){
        if (b[i] % 2 == 0) t ++;// 偶数说明是开始时间，开教室
        else t --;// 奇数说明是结束时间，关教室
        res = max(res,t);
    }
    cout << res << '\n';
    return 0;
}

这个思路最妙的地方就在于用奇偶变换来解决区间端点相交的问题。

给一组样例：

1
2
3

2
1 5
5 7

按照代码，我们会按照b数组中的值从小到大排序。

当两个不相等的端点排序（l != r）时，根据b数组的奇偶变换公式，端点坐标小的肯定排在前面；
当两个相等的端点排序时（l == r），根据b数组的奇偶变换公式，l一定会排在r的前面。

根据题目要求，端点相交不能放在一组，也就是说，当一个活动的结束时间刚好等于另一活动的开始时间时，必须得开2间教室才行。上面说了，两个相等的端点，l一定会排在r的前面。所以先判断l是否为奇数，开1间教室，计算最大教室数，然后判断r是否为奇数，关1间教室，计算最大教室数。所以同时开的最大教室数就是2。

如果能区间端点能重合的话，端点标记的奇数偶数反一下就行了。

算法2：区间贪心。

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 1e5+5;

pair<int,int> range[N];// 存放区间，默认按第一维排序

int main(){
    int n;
    scanf("%d",&n);

    int l,r;
    for (int i = 0;i < n;i ++){
        scanf("%d%d",&l,&r);
        range[i] = {l,r};
    }

    sort(range,range+n);// 按左端点排序
    priority_queue<int,vector<int>,greater<int> > heap;// 定义小根堆

    for (int i = 0;i < n;i ++){// 处理每一个区间
        if (heap.empty() || range[i].first <= heap.top()) // 堆空或者当前区间与堆顶相交
            heap.push(range[i].second);// 则开新的小组
        else{
            heap.pop();// 否则更新堆顶所在小组
            heap.push(range[i].second);
        }
    }
    printf("%d\n",heap.size());
    return 0;
}

grant's Blog

算法基础课笔记（三十）

五：贪心

5.1：区间问题