狂暴的老师 - 优化排队顺序，最小化老师的狂暴程度

题目背景

有 $n$ 个同学（从 $0$ 开始编号）在学习信奥课，同学们排队向老师提问。每个同学问的问题不同，因此答疑时长不同，设第 $i$ 个同学的答疑时长为 $t_i$；每个同学的耐心值也不同，设第 $i$ 个同学的耐心为 $p_i$。 如果一个同学等待太久，他会暴躁。每个同学的暴躁程度 $g_i$ 等于排在他前面的同学的答疑时长之和与自身耐心的差值，即：$g_i = \sum_{j=0}^{i-1}t_j - p_i$。 如果同学们很暴躁，老师会狂暴。老师的狂暴程度 $r$ 等于所有同学暴躁程度 $g_i$ 的最大值，即：$r = \max_{i=0}^{n-1}g_i$。 改变 $n$ 个同学的排队顺序，老师的狂暴程度可能会发生变化。求所有的排队顺序中，老师的狂暴程度的最小值 $\min r$。

题目描述

输入格式

从标准输入读入数据。 第一行为一个正整数 $n$（$1 \le n \le 1,000$），表示有 $n$ 位同学。 第二行到第 $n+1$ 行，每行两个整数，分别是 $t_i$（$0 \le t_i \le 1,000$）和 $p_i$（$0 \le p_i \le 1,000$）。

输出格式

输出到标准输出。 输出共一行，表示老师狂暴程度 $r$ 的最小值。

样例 #1

样例输入 #1

3
5 1
1 4
2 2

样例输出 #1

2

算法

算法1

(二分答案) $O(n\log n)$

首先可以考虑二分答案，答案 $mid$ 表示老师狂暴程度的最大值，然后检验是否可行。

检验是否可行的时候可以用贪心，将同学按照答疑时间从小到大排序，然后依次加入队列，如果加入后队列中的最大暴躁程度 $maxg$ 大于 $mid$，则需要弹出队首的同学，直到 $maxg$ 不大于 $mid$，然后继续加入下一个同学。

时间复杂度：$O(n\log^2 n)$，其中一重 $\log$ 是二分答案，另外一重 $\log$ 是排序。

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1000;

int n;
int t[MAXN], p[MAXN];

bool check(int mid) {
    int maxg = 0;
    int q[MAXN], head = 0, tail = 0;
    for (int i = 0; i < n; i++) {
        while (head < tail && t[q[head]] + t[i] - p[i] > mid) {
            head++;
        }
        q[tail++] = i;
        maxg = max(maxg, t[q[tail - 1]] - p[q[tail - 1]]);
        if (maxg > mid) {
            return false;
        }
    }
    return true;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> t[i] >> p[i];
    }
    int l = 0, r = 1000 * n;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    cout << l << endl;
    return 0;
}

算法2

(单调队列) $O(n)$

上面的算法中，每次检验是否可行都需要排序，时间复杂度较高。可以考虑优化这一部分。

由于当加入一个新的同学时，需要弹出队首，因此可以想到用单调队列来维护队列中的最大暴躁程度。

具体来说，用一个单调递减的队列 $q$ 来存储同学的编号，队列中的同学按照答疑时间从小到大排列。依次加入同学 $i$，当队首的同学 $j$ 的答疑时间和 $i$ 的答疑时间之差大于 $mid$ 时，需要弹出 $j$，直到队首的同学 $k$ 的答疑时间和 $i$ 的答疑时间之差不大于 $mid$。在弹出同学 $j$ 后，队列中剩下的同学的暴躁程度会发生变化，但是只有新增加的同学 $i$ 可能会使得暴躁程度变大，因此只需要更新队首到同学 $i$ 之间的同学的暴躁程度即可。具体来说，设 $q$ 中的同学编号为 $j_1,j_2,\dots,j_k$，则在加入同学 $i$ 之前，$q$ 中的同学的暴躁程度 $g_{j_1},g_{j_2},\dots,g_{j_k}$ 满足 $g_{j_1} \ge g_{j_2} \ge \dots \ge g_{j_k}$。加入同学 $i$ 后，需要更新 $q$ 中的同学的暴躁程度，具体来说，对于 $j_1,j_2,\dots,j_k$ 中的每个同学 $j$，要将 $g_j$ 更新为 $g_j + t_j - p_i$。

时间复杂度：$O(n)$。

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1000;

int n;
int t[MAXN], p[MAXN];

bool check(int mid) {
    int q[MAXN], head = 0, tail = 0;
    int maxg = 0;
    for (int i = 0; i < n; i++) {
        while (head < tail && t[q[head]] + t[i] - p[i] > mid) {
            head++;
        }
        q[tail++] = i;
        if (head < tail) {
            maxg = max(maxg, t[q[head]] - p[q[head]]);
        }
        for (int j = head; j < tail; j++) {
            t[q[j]] += t[i] - p[i];
        }
        if (maxg > mid) {
            return false;
        }
    }
    return true;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> t[i] >> p[i];
    }
    int l = 0, r = 1000 * n;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    cout << l << endl;
    return 0;
}