贪心 | OI笔记

贪心

从局部最优推向全局最优

基本思想

始终做出当前最优选择，从而期望全局达到最优。值得注意的是，如果当前最优选择无法保证推出全局最优解，我们可以更换策略如动态规划

贪心证明

贪心不证明，亲人两行泪

1. 反证法: 对于当前的贪心策略，否定当前的选择来证明是否能达到最优解
2. 构造法: 将问题构造成已知的算法或数据结构从而证明贪心册罗正确
3. 数学推导

反证法的应用实例：
洛谷p1650 - 田忌赛马

贪心策略：

1. 如果田忌目前的最快🐎快于齐王的最快马，则两者比
2. 如果田忌的最快马慢于齐王的最快马，则用田忌的最慢马与齐王的最快马比
3. 如果两者的最快马速度相等，则：
   1. 若田忌的最慢马快于齐王的最慢马，则两个最慢马比
   2. 若田忌的最慢马慢于齐王的最慢马或者两者相等，则用田忌的最慢马与齐王的最快马比

AC代码：

int hs1[N], hs2[N];
int n, mny;

cin >> n;
for (int i = 1; i <= n; i ++)
    cin >> hs1[i];
for (int i = 1; i <= n; i ++)
    cin >> hs2[i];

sort (hs1 + 1, hs1 + n + 1, greater<int>());
sort (hs2 + 1, hs2 + n + 1, greater<int>());
// input

int l1 = 1, r1 = n, l2 = 1, r2 = n;
// 1 refers to TianJi, 2 refers to the King

while (l1 <= r1 && l2 <= r2)
    if (hs1[l1] > hs2[l2]) l1 ++, l2 ++, mny ++;
    else if (hs1[l1] < hs2[l2]) r1 --, l2 ++, mny --;
    else 
        if (hs1[r1] > hs2[r2]) r1 --, r2 --, mny ++;
        else 
        {
            if (hs1[r1] < hs2[l2]) mny --;
            r1 --, l2 ++;
        }
        
cout << mny * 200 << endl;

区间问题

选择不相交的区间

数轴上有 $n$ 个区间，每条线段都有起点和终点，选择最多的不相交的线段个数。

最优的贪心策略为：对右端点进行排序，一次选择左端点大于前一个已经选择的右端点的区间

区间选点问题

数轴上有 $n$ 个闭区间 [a, b] 。取尽可能少的点，使得每个区间内都至少有一个点 （不同区间内含的点可以是同一个）。

洛谷p1325 - 雷达安装

最优的贪心策略为：右端点升序排列，右端点相等的左端点降序

区间覆盖问题

数轴上有n个闭区间 [a, b] ，选择尽量少的区间覆盖一条指定线段 [s,t] 。

洛谷p2082 - 区间覆盖（加强版）

基本策略：

区间合并问题

数轴上有n个闭区间 [a, b] ，求能够覆盖的长度。

以左端点升序排列，选取第一条线段，之后在所有前端点小于当前右端点的情况中选右端点最大的线段，继续更新

代码详见区间合并