贪心(Greedy Algorithm)

这个带有些许贬义的名字可以直观看出算法的,因为想要最多的所以目光短浅，每一步选择都采取当下选择最优解，从而导致全局最优的算法策略

核心思想

  1. 局部最优从而导致全局最优
  2. 不会回溯：一旦做出选择就不再改变或者回退
  3. 短视性

应用

  1. 活动选择（安排最多但是不冲突的活动
  2. 霍夫曼编码（数据压缩
  3. 最小生成树
  4. 最短路径
  5. 硬币找零
  6. 分数背包问题

（让我慢慢遇见这些问题吧。。。

在看见贪心算法时大家应该会有一种稍稍怀疑但是喜悦的感觉，因为如此省心就可以解决问题，实则不然，在使用贪心算法前，一定要严格证明这个问题是具有贪心性质的！！！

1.合并果子

题目：在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并,多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 n−1 次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 1，并且已知果子的种类 数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有 3 种果子，数目依次为 1，2，9。可以先将 1、2 堆合并，新堆数目为 3，耗费体力为 3 。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 12，耗费体力为 12。所以多多总共耗费体力 =3+12=15。可以证明 15 为最小的体力耗费值。

解读
这是一个经典的合并果子问题。优先队列（最小堆）解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
#include<queue>
using namespace std;

int main(){
    int n;
    cin>>n;

    //最小堆
    priority_queue<int,vector<int>,greater<int>> q;

    for(int i=0;i<n;i++){
        int w;
        cin>>w;
        q.push(w);
        //最小的会在顶部
    }

    long long ans=0;
    //至少需要两个元素才会合并
    while(q.size()>1){
        int a=q.top();q.pop();
        int b=q.top();q.pop();

        int s=a+b;
        ans+=s;
        q.push(s);
    }

    cout<<ans<<endl;
    return 0;
}

Q:为啥这种算法就能精力消耗最小呢?

ans:合并次数是固定的：n堆果子需要n-1次合并

每个果子的重量在总代价中被计算的次数等于它在树中的深度

要最小化总代价，应该让重的果子尽量少被合并（放在浅层），轻的果子可以多被合并（放在深层）。

豁然开朗

2.彻底怒了

贪心问题总是判断出过后要写出合理的代码实现，但是却往往卡在这一步。分析归类此题需要用何种方法解决其实是第一步也是最重要的一步，但这并不意味着万事大吉

题目描述

金将军有两个长度为 n 的字符串 s,t，他认为一个字符串的愤怒值为其 CDNL 子串的个数。

现在，他想在 s 中选出一个长度至多为 m的子串 s’，在 t 中选出一个长度至多为 k 的子串 t’，使 s’,t’ 按顺序拼接后的字符串的愤怒值最大，你需要帮他求出这个值。

子串为原字符串中连续的一段字符组成的字符串。

碎碎念

笔者卡住的原因是跨界情况比较复杂，且内部匹配数的快速计算需要滑动窗口技巧，不是简单贪心能一次得到。
这个问题其实是一个受限最值子串选取+拼接模式匹配的优化问题，需要分情况仔细讨论并预处理，一想到会有不同的拼接情况，so nerve-racking

三种情况

如果列举的话

  1. 只出现在前一个字符串里且都为整个的连续子串，另一个字符串贡献为零
  2. 互换过来
  3. 都有贡献而且两者拼接部分不整，共同在拼接处形成一个CDNL

期末周结束我会回来的。。。