贪心专题

简述

我贪心太菜了,所以来总结几种模型,以防赛场 GG。

扰动排序

扰动排序的经典例题就是国王游戏了。通过对已知的序列顺序进行分析,然后找出排序规律。

Johnson 法则

这个东西会出现在加工生产调度问题中,大概问题的描述就是(来自洛谷):

某工厂收到了n个产品的订单,这n个产品分别在A、B两个车间加工,并且必须先在A车间加工后才可以到B车间加工。

某个产品i在A、B两车间加工的时间分别为Ai、Bi。怎样安排这n个产品的加工顺序,才能使总的加工时间最短。这里所说的加工时间是指:从开始加工第一个产品到最后所有的产品都已在A、B两车间加工完毕的时间。

对于这个问题,定义一个\(d_i\)来帮助排序:

\[ d_i = \begin{cases} -1, a_i < b_i \\ 0, a_i = b_i \\ 1, a_i > b_i \end{cases} \]

如果\(d_i\)不同,则先按照\(d_i\)进行排序;如果相同,那么对于\(d_i \leq 0\)的情况,按照\(a_i\)升序排序;对于\(d_i > 0\)的情况,按照\(b_i\)做降序排序。

具体代码:

// P1248.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1010;

struct node
{
    int a_time, b_time, d, id;

    bool operator<(const node &nd) const { return d == nd.d ? min(a_time, nd.b_time) < min(b_time, nd.a_time) : d < nd.d; }
} nodes[MAX_N];

int n;

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &nodes[i].a_time), nodes[i].id = i;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &nodes[i].b_time);
        nodes[i].d = nodes[i].a_time < nodes[i].b_time ? -1 : (nodes[i].a_time > nodes[i].b_time ? 1 : 0);
    }
    sort(nodes + 1, nodes + 1 + n);
    long long T_A = nodes[1].a_time, T_B = nodes[1].a_time + nodes[1].b_time;
    for (int i = 2; i <= n; i++)
        T_B = max(T_A + nodes[i].a_time, T_B) + nodes[i].b_time, T_A += nodes[i].a_time;
    printf("%lld\n", T_B);
    for (int i = 1; i <= n; i++)
        printf("%d ", nodes[i].id);
    return 0;
}

堆的一些贪心

经典例题 1    [APIO2007]数据备份

这道题用链表来把一起选上的合并在一起,然后用堆的方式来进行反悔。这样的题还有经典例题「种树」。

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注