[Note] 贪心策略

[L4] 贪心策略

1. 生态位

• 识别:

  1. 目标函数为单峰或具有明显的局部单调性。

  2. 决策序列具有无后效性：当前的决策不会改变过去，也不受未来尚未发生决策的影响。

  3. 存在某种“排序”或“结构”，使得局部最优可以直接推导出全局最优。

• 定义: 在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致全局最优的算法范式。

• 地位: 是一种算法直觉。贪心不需要维护复杂的 DP 维度，它是通过发现特殊的贪心条件来降维复杂度。

• 用途: 贪心通常作为 $O(N \log N)$ 或 $O(N)$ 的高效算子，用于处理最优化问题，或者作为复杂算法（如 Prim、Dijkstra）的逻辑内核。

2. 逻辑支点

2.1 贪心证明：邻项交换

• 很多贪心排序规则（如 $a.t / a.w < b.t / b.w$）不是直觉猜的，而是推出来的。

• 推导逻辑: 假设当前序列是最优的。如果我们交换相邻的两个元素 $i$ 和 $i+1$，整体代价变大。通过化简这个不等式，就能反推出排序的判定准则。

2.2 核心模型 I：哈夫曼树

• 逻辑: 每次合并两个代价最小的节点。

• 物理意义: 越早合并的节点，被重复计算的次数越多。因此，让权值小的节点沉到底部，能使总权值和（$\sum \text{weight} \times \text{depth}$）最小。

• 演化: 从 $O(N \log N)$ 的优先队列优化到 $O(N)$ 的双队列优化（前提是输入序列已有序）。

2.3 核心模型 II：区间调度与覆盖

• 模型 A (不相交区间最大化): 按右端点排序。

• 逻辑：给后面留下的空间越多，能放的区间越多。

• 模型 B (区间覆盖): 按左端点排序。

• 逻辑：在覆盖当前起点的基础上，尽可能向右延伸。

2.4 核心模型 III：反悔贪心

• 中译中: “我现在先选个最好的，如果后面发现选错了，我可以用代价最小的方式把它换掉。”

• 工具: 通常配合堆（Heap）实现，记录已做出的决策，动态撤销代价最高的局部方案。

3. 实战部署

▶

代码实现: 哈夫曼树 (双队列优化 O(N))

// 场景：已知权值 a 已经有序，求最小合并代价
ll solve_huffman( int n )
{
    // q1 存放原始有序序列，q2 存放新合成的序列
    // head1, head2 为各自队首
    ll total_cost = 0;
    
    auto get_min = [ & ]( ) -> long long {
        if( head1 > n ) return q2[ head2 ++ ];
        if( head2 > tail2 ) return q1[ head1 ++ ];
        return ( q1[ head1 ] < q2[ head2 ] ) ? q1[ head1 ++ ] : q2[ head2 ++ ];
    };

    for( int i = 1; i < n; ++ i )
    {
        ll m1 = get_min( );
        ll m2 = get_min( );
        ll res = m1 + m2;
        total_cost += res;
        q2[ ++ tail2 ] = res; // 新合成的 res 天然满足单调性
    }
    return total_cost;
}

▶

代码实现: 反悔贪心标准算子

// 场景：受限资源下的最大化收益
priority_queue< int > pq;
ll current_profit = 0;

for( int i = 1; i <= n; ++ i )
{
    if( check( task[i] ) )
    {
        pq.push( task[i].val );
        current_profit += task[i].val;
    }
    else if( !pq.empty( ) && task[i].val > pq.top( ) )
    {
        // 发现更好的选择，撤销之前收益最小的决策
        current_profit -= pq.top( );
        pq.pop( );
        pq.push( task[i].val );
        current_profit += task[i].val;
    }
}

4. 知识关联

• 母题:

  • P6033 合并果子: 经典的贪心合并模型。

• 实战案例:

  • [[ABC441C Sake and Water]]: 贪心构造最坏情况，寻找不变量。
  • CF2182E New Year's Gifts: 双重资源约束下的代价匹配与贪心平衡。
  • CF2183B Yet Another MEX Problem: 构造思维下的 MEX 核心结论。
  • CF2183C War Strategy: 寻找区间扩张的强制性规律与步数贪心。

• 关联笔记:

  • 排序体系: 排序是贪心的“前置技能”。
  • 浅谈二分答案：很多时候“二分答案”里的 check 函数就是靠贪心跑出来的。
  • [[动态规划]]: 当贪心的“无后效性”失效时，必须升维至 DP。