简述

我贪心太菜了，所以来总结几种模型，以防赛场 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;
}