信奥课排队问题：最小化老师狂暴程度

信奥课排队问题：最小化老师狂暴程度/n/n有 $n$ 个同学（从 $0$ 开始编号）在学习信奥课，同学们排队向老师提问。每个同学问的问题不同，因此答疑时长不同，设第 $i$ 个同学的答疑时长为 $t_i$；每个同学的耐心值也不同，设第 $i$ 个同学的耐心为 $p_i$。/n如果一个同学等待太久，他会暴躁。每个同学的暴躁程度 $g_i$ 等于排在他前面的同学的答疑时长之和与自身耐心的差值，即：$g_i=/sum_{j=0}^{i-1}t_j-p_i$。/n如果同学们很暴躁，老师会狂暴。老师的狂暴程度 $r$ 等于所有同学暴躁程度 $g_i$ 的最大值，即：$r=/max_{i=0}^{n-1}g_i$。/n改变 $n$ 个同学的排队顺序，老师的狂暴程度可能会发生变化。求所有的排队顺序中，老师的狂暴程度的最小值 $/min r$。/n/n### 题目描述/n/n### 输入格式/n/n从标准输入读入数据。/n第一行为一个正整数 $n$（$1/le n/le1,000$），表示有 $n$ 位同学。/n第二行到第 $n+1$ 行，每行两个整数，分别是 $t_i$（$0/le t_i/le 1,000$）和 $p_i$（$0/le p_i/le 1,000$）。/n/n### 输出格式/n/n输出到标准输出。/n输出共一行，表示老师狂暴程度 $r$ 的最小值。/n/n### 样例 #1/n/n#### 样例输入 #1/n/n/n3/n5 1/n1 4/n2 2/n/n/n#### 样例输出 #1/n/n/n2/n/n/n写一个C++代码内容：题目的要求是求最小值，可以考虑使用二分答案来解决。具体来说，二分答案 $mid$，然后检查是否存在一种排队顺序，使得老师的狂暴程度不超过 $mid$。/n/n对于检查的部分，我们可以使用贪心算法。把所有同学按照 $t_i-p_i$ 从小到大排序，然后从前往后一个一个安排排队顺序。如果当前同学不能等待，就把他放到队尾；如果当前同学能等待，就让他排队等待。当所有同学都被安排完后，检查老师的狂暴程度是否小于等于 $mid$。/n/n时间复杂度 $O(n /log n)$。/n/n代码：/n/ncpp/n#include <iostream>/n#include <algorithm>/nusing namespace std;/n/nconst int MAXN = 1000;/n/nint n, t[MAXN], p[MAXN];/n/nbool check(int mid) {/n int waitTime = 0;/n int g[MAXN] = {0};/n for (int i = 0; i < n; ++i) {/n if (waitTime + t[i] - p[i] <= mid) {/n g[i] = waitTime + t[i] - p[i];/n waitTime += t[i];/n } else {/n g[n - 1] = waitTime + t[i] - p[i];/n waitTime = t[i];/n }/n }/n int maxG = g[0];/n for (int i = 1; i < n; ++i) {/n maxG = max(maxG, g[i]);/n }/n return maxG <= mid;/n}/n/nint main() {/n cin >> n;/n for (int i = 0; i < n; ++i) {/n cin >> t[i] >> p[i];/n }/n int l = 0, r = 1000 * n;/n while (l <= r) {/n int mid = (l + r) / 2;/n if (check(mid)) {/n r = mid - 1;/n } else {/n l = mid + 1;/n }/n }/n cout << l << endl;/n return 0;/n}/n/n