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

题目大意/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$（$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## 思路/n/n首先我们要对题目中的 $r$ 值进行分析，这个值等于所有学生的暴躁程度的最大值，因此，如果我们要求得最小的 $r$ 值，那就要在满足所有学生要求的前提下，尽可能缩小暴躁程度的最大值，这里我们可以采用二分答案的思想。/n/n对于二分答案的思想，我们需要先进行一些准备工作，首先是对答案范围的确定。在做这道题时，我们可以发现 $r$ 的取值范围是在所有学生的答疑时长中的最大值 $t$ 和所有学生的耐心值中的最大值 $p$ 之间，因此我们可以对这个范围进行二分。/n/n接下来，我们就要考虑如何进行二分了，这里我们可以采用贪心的思想。我们将所有同学按照答疑时长从小到大排列，然后对于每个同学，我们将其插入到所有已经排好序的同学当中，考虑这个同学的暴躁程度是否大于等于当前的答案，如果大于等于答案，那么就意味着这个同学会让老师狂暴，因此我们就要将这个同学插入到下一个位置，直到找到一个合适的位置。/n/n在找到合适的位置之后，我们可以继续对下一个同学进行插入操作，直到所有的同学都排好序为止。最后，如果所有同学的暴躁程度都小于答案，那么就意味着当前的答案是可行的，因此我们可以将答案缩小到 $[l,mid]$，否则就将答案扩大到 $[mid+1,r]$。/n/n## 代码/n/ncpp/n#include <iostream>/n#include <algorithm>/n#include <vector>/n/nusing namespace std;/n/nconst int MAXN = 1000;/n/nint n;/nint t[MAXN], p[MAXN];/n/nbool check(int r) {/n vector<int> order;/n long long sum = 0;/n for (int i = 0; i < n; i++) {/n int j = 0;/n while (j < order.size() && sum + t[order[j]] - p[i] >= r) {/n j++;/n }/n order.insert(order.begin() + j, i);/n sum += t[i];/n }/n return order.size() == n;/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 = *max_element(t, t + n);/n while (l <= r) {/n int mid = (l + r) >> 1;/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