贪心算法，是寻找最优解问题的常用方法，这种方法模式一般将求解过程分成若干个步骤，但每个步骤都应用贪心策略，选取当前状态下最好/最优的选择（局部最优解），并以此希望最后堆叠出的结果也是最好/最优的解。

贪心算法入门(Greedy algorithm)

解决贪心问题的基本步骤

将原问题分解为子问题
找出贪心策略
得到每一个子问题的最优解
将所有局部最优解的集合构成称为原问题的一个解

思路分析

贪心算法的根本$\implies$策略的选择

贪心算法的根本在于贪心策略的选择，如果能找出正确的贪心策略的话，贪心问题也就迎刃而解。

贪心策略:即我们需要找到一种方法使得当前可以获得的收益最大。举个栗子:我们每个人都对未来有很多憧憬和计划。我们希望我们的人生都能得到最优解。但是由于我们无法预知之后几年几十年的事情发展，我们无法精准地计算出我们在每一个时间节点的完美选择。于是我们只好选择每一天，或者当前时间段我都做对自己最有帮助的事情。经过不断地积累最后得到最终结果，未必不是一种好的做法。

例题分析

P1090 合并果子

题目描述

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 $n-1$ 次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

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

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

输入格式

共两行。
第一行是一个整数 $n(1\leq n\leq 10000)$ ，表示果子的种类数。

第二行包含 $n$ 个整数，用空格分隔，第 $i$ 个整数 $a_i(1\leq a_i\leq 20000)$是第 $i$ 种果子的数目。

输出格式

一个整数，也就是最小的体力耗费值。输入数据保证这个值小于 $2^{31}$

说明/提示

对于$30％$的数据，保证有$n \le 1000$：
对于$50％$的数据，保证有$n \le 5000$；
对于全部的数据，保证有$n \le 10000$。

洛谷P1090

既然是贪心的思想:那么就首先要将问题分解成为子问题，然后着眼于子问题的最优解，最后将所有子问题的最优解汇总即可

$n$堆的果子一定会经过$n-1$次合并,而每次消耗的体力之和为两堆果子的重量。其实很明显，我们要先搬重量小的那些堆，因为这样重的堆就不会被多次搬运而被算入被消耗地体力。

我们也就可以得出这道题最终要采用的贪心策略:每次取出两个最小的进行合并，合并完后再将新的堆存入，再进行重复操作。由于这里涉及到了排序，最优的方法就是用STL里的堆。

AC代码如下:

#include <bits/stdc++.h>//建议不要使用万能头QwQ
using namespace std;

priority_queue<int,vector<int>,greater<int> > qwq;
int n;
int main(){
    cin>>n;
    int x,a,b,ans = 0;
    for(int i = 0;i<n;i++){
        cin>>x;
        qwq.push(x);
    }
    
    while(qwq.size()>=2){
        a = qwq.top();
        qwq.pop();
        b = qwq.top();
        qwq.pop();
        ans += (a+b);
        qwq.push(a+b);
    }

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

P1253 线性存储问题

洛谷P1253

这道题的贪心策略也很明显，我们可以把$L_i\times F_i$看做查询一个数据的时间，那么我们就可以将时间长的放在前面。

由于要储存三个数据($L_1$、$F_i$、编号$i$),所以我这里选择使用结构体+sort+自定义函数来解决排序问题

AC代码如下:

#include <bits/stdc++.h>
using namespace std;

struct qwq{
    int l,f,i;
}orz[10002];

bool cmp(qwq a,qwq b){
    return (a.l*a.f > b.l*b.f);
}

int main(){
    int n;
    cin>>n;
    for(int j = 1;j <= n;j++){
        cin>>orz[j].l>>orz[j].f;
        orz[j].i = j;
    }

    sort(orz+1,orz+1+n,cmp);

    for(int j = 1;j <= n;j++){
        cout<<orz[j].i<<" ";
    }

    return 0;
}

存在的问题和难点

证明困难，大部分的贪心算法难以证明
大部分情况下其实并不是最优解
贪心问题之间的跨越度比较大