贪心专题

简述

我贪心太菜了,所以来总结几种模型,以防赛场 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   元旦晚会

考虑把所有线段按照右端点排序,然后优先把右端点左右的同学染上色,这样可以保证交集最大。(贪心啊)

例题 2   JZOJ???? 梦境

把点先排序,然后再把能放入的区间加入到堆中、非法的区间退出堆中。此时发现显然选择最右的会更优。

堆的一些贪心

例题 1    [APIO2007]数据备份

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

例题 2   CF1158A The Party and Sweets

我写了这道题目的非正解:也就是用堆。考虑先把男生提供的最小值放上去,再来考虑把一些最小值分配给女生,以修改成最大值。我们可以记录男生被修改了多少次,然后再特判大小值的情况即可。

// CF1159C.cpp
#include <bits/stdc++.h>
#define ll long long
#define pr pair<int, int>

using namespace std;

const int MAX_N = 1e5 + 200;

int n, m, ai[MAX_N], bi[MAX_N], cnt[MAX_N];
ll ans;

int main()
{
    int mx_val = 0;
    scanf("%d%d", &n, &m);
    priority_queue<pr> pq;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &ai[i]), ans += 1LL * ai[i] * m, cnt[i] = m, mx_val = max(mx_val, ai[i]);
        pq.push(make_pair(ai[i], i));
    }
    for (int i = 1; i <= m; i++)
    {
        scanf("%d", &bi[i]);
        if (bi[i] < mx_val)
            puts("-1"), exit(0);
    }
    sort(bi + 1, bi + 1 + m);
    for (int i = m; i >= 1; i--)
    {
        while (!pq.empty() && cnt[pq.top().second] < 2 && pq.top().first < bi[i])
            pq.pop();
        if (pq.empty())
            puts("-1"), exit(0);
        pair<int, int> p = pq.top();
        cnt[p.second]--, ans += bi[i] - p.first, pq.pop(), pq.push(p);
    }
    printf("%lld", ans);
    return 0;
}

 

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

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