# 贪心

贪心算法（英语：greedy algorithm），是用计算机来模拟一个「贪心」的人做出决策的过程。这个人十分贪婪，每一步行动总是按某种指标选取最优的操作。而且他目光短浅，总是只看眼前，并不考虑以后可能造成的影响。

可想而知，并不是所有的时候贪心法都能获得最优解，所以一般使用贪心法的时候，都要确保自己能证明其正确性。

简单来说，就是当前状态下只取当前状态的最优解

# 适用范围

贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。

# 贪心常见题型

# 排序解法

用排序法常见的情况是输入一个包含几个（一般一到两个）权值的数组，通过排序然后遍历模拟计算的方法求出最优值。

# 后悔解法

思路是无论当前的选项是否最优都接受，然后进行比较，如果选择之后不是最优了，则反悔，舍弃掉这个选项；否则，正式接受。如此往复。

# 例题讲解

# 部分背包问题

题目描述：

我们有一个背包，它能够承载的重量是 W。现在，我们希望往包里装一些物品，这些物品具有一定的重量和价值，每个物品都可分解，分解前后单位重量价值不变，求背包能装下的最大价值

思路：

因为物品是可拆卸的，因此我们每次只需要将单位价值最大的物品装进包里就行，如果装不下就把物品进行分解即可

代码：

struct node {

    int val, v;

    double p;

    bool operator<(const node &a) const { return p > a.p; }

} a[N];

int n, t;

void solve() {

    cin >> n >> t;

    for (int i = 1; i <= n; i++)

        cin >> a[i].v >> a[i].val, a[i].p = 1.0 * a[i].val / a[i].v;

    sort(a + 1, a + 1 + n);

    double ans = 0, v = 0;

    for (int i = 1; i <= n; i++) {

        if (v + a[i].v <= t) {

            ans += a[i].val;

            v += a[i].v;

        } else {

            ans += 1.0 * (t - v) / a[i].v * a[i].val;

            break;

        }

    }

    cout << ans << '\n';

}

# 合并果子

题目描述：

给你一些果子，每次可以合并两个堆合并成一个堆，消耗体力为两堆重量之和，最终求合并成一个堆所消耗体力的最小值

思路：

如何贪心呢？越先合并的那堆果子，它的重量将被添加的更多，所以要得到最小的体力耗费值，要将每次最小的两堆合并。（找最小值和次小值），因为每次合并堆的体力一定是逐渐递增的，所以我们使用一个队列来存放合并的堆

代码：

int n, a[N], b[N], m;

void solve() {

    memset(a, 0x3f, sizeof(a));

    memset(b, 0x3f, sizeof(b));

    int ans = 0;

    cin >> n;

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

    sort(a + 1, a + 1 + n);

    int l = 1, r = 1, x, cnt = 1;

    while (cnt <= n - 1) {

        if (a[l] < b[r])

            x = a[l++];

        else

            x = b[r++];

        if (a[l] < b[r])

            x += a[l++];

        else

            x += b[r++];

        cnt++;

        ans += x;

        b[++m] = x;

    }

    cout << ans << '\n';

}

# 国王游戏

# 题目描述:

国王和大臣左右手都有一个整数，每位大臣获得的金币数是排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。现在你可以调整大臣的位置，求获得奖赏最多的大臣金币数的最小值

# 思路:

根据题意我们可以知道，大臣 1 和大臣 2 位置能交换的必要条件是：大臣 2 放在大臣 1 的前面得到的最大值更加小。那么我们分别讨论两种情况下的最大值，假设只有两个大臣：
如果大臣 1 放在前面，他俩获得的金币数分别为：
$a_0/b_1$,$a_0*a_1/b_2$
如果大臣 2 放在前面，他俩获得的金币数分别为：
$a_0/b_2$,$a_0*a_2/b_1$
首先，我们约去式子里面的 a0，然后分别讨论两种情况的最大值，就变成了比较：
$max(1/b_1,a_1/b_2)$ 和$max(1/b_2,a_2/b_1)$ 的大小
根据$0<a$,$a$ 是整数的条件，我们可以得出:
$a_1/b_2$ $\geq$ $1/b_2、1/b_1$ $\leq$ $a_2/b_1$
那么，如果$1/b_1$ 是最大的，则有
$1/b_1$ $\geq$ $a_2/b_1$，只可能左右两边相等，则有$1/b_2$$\leq$$a_2/b_1$，所以两种情况的最大值是一样的，则不用交换。
同理可得$1/b_2$ 是最大的情况也不用交换。
那么我们就只要$a_1/b_2$ 和$a_2/b_1$ 的大小就可以了，也就是说如果$a_1/b2$ $\gt$ $a_2/b_1$，那么就要交换，变形得：
$a_1*b_1$ $\gt$ $a_2*b_2$
表示要交换，我们排序就只要按照$a*b$ 的从小到大排就可以了。

# 代码:

struct node {

    ll x, y;

    bool operator<(const node &a) const { return x * y < a.x * a.y; }

} dc[N];

ll n, a, b;

void solve() {

    cin >> n >> a >> b;

    for (int i = 1; i <= n; i++) cin >> dc[i].x >> dc[i].y;

    sort(dc + 1, dc + 1 + n);

    ll ans = 0, now = a;

    for (int i = 1; i <= n; i++) {

        ans = max(ans, now / dc[i].y);

        now *= dc[i].x;

    }

    cout << ans << '\n';

}

# 工作调度 Work Scheduling

反悔贪心

# 题目描述:

约翰的工作日从 $0$ 时刻开始，有 $10^9$ 个单位时间。在任一单位时间，他都可以选择编号 $1$ 到 $N$ 的 $N(1 \leq N \leq 10^5)$ 项工作中的任意一项工作来完成。工作 $i$ 的截止时间是 $D_i(1 \leq D_i \leq 10^9)$，完成后获利是 $P_i( 1\leq P_i\leq 10^9 )$。在给定的工作利润和截止时间下，求约翰能够获得的利润最大为多少。

# 解题思路:

1. 先假设每一项工作都做，将各项工作按截止时间排序后入队；
2. 在判断第 i 项工作做与不做时，若其截至时间符合条件，则将其与队中报酬最小的元素比较，若第 i 项工作报酬较高（后悔），则 ans += a [i].p - q.top ()。
   用优先队列（小根堆）来维护队首元素最小。
3. 当 a [i].d<=q.size () 可以这么理解从 0 开始到 a [i].d 这个时间段只能做 a [i].d 个任务，而若 q.size ()>=a [i].d 说明完成 q.size () 个任务时间大于等于 a [i].d 的时间，所以当第 i 个任务获利比较大的时候应该把最小的任务从优先级队列中换出。

# 代码:

struct A {

    ll d, p;

    bool operator<(const A &a) const { return d < a.d; }

} a[N];

priority_queue<ll, vector<ll>, greater<ll>> q;

ll n;

void solve() {

    ll ans = 0;

    cin >> n;

    for (int i = 1; i <= n; i++) cin >> a[i].d >> a[i].p;

    sort(a + 1, a + 1 + n);

    for (int i = 1; i <= n; i++) {

        if (a[i].d <= (ll)q.size()) {

            if (a[i].p > q.top()) {

                ans += a[i].p - q.top();

                q.pop();

                q.push(a[i].p);

            }

        } else {

            ans += a[i].p;

            q.push(a[i].p);

        }

    }

    cout << ans << '\n';

}