信奥老师的狂暴：求解最小狂暴程度

信奥老师的狂暴：求解最小狂暴程度/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## 代码/n/n### 算法1 (二分答案) $O(n/log n)$/n/n首先，我们可以想到一个 $O(n^2)$ 的做法：枚举排列，计算老师狂暴程度 $r$，并取最小值。/n但是，$n$ 最大为 $1,000$，所以这个算法最多只能得到 $1,000,000$ 分，无法通过本题。/n考虑优化这个算法。如果我们知道了一个排列，如何判断老师狂暴程度是否 $/leq r$ 呢？可以按照答疑时长 $t_i$ 从小到大进行模拟。每当老师答完一个同学的问题时，我们可以更新该同学之后的暴躁程度 $g_i$。如果 $g_i$ 第一次 $/geq r$，我们就可以退出模拟并返回 false（即无法满足 $/min r$ 的条件）。/n问题转化为：如何求出老师狂暴程度 $r$ 是否 $/leq x$。我们可以二分答案，假设当前二分的答案为 $mid$，那么我们只需要假设所有的 $g_i/leq mid$，然后按照上面的方法模拟即可。如果能够模拟成功，说明 $r/leq mid$，反之 $r>mid$。这种方法的时间复杂度为 $O(n/log n/log (10^6n))$，可以通过本题。/n/n#### 时间复杂度/n/n$O(n/log n/log (10^6n))$ /n/n#### 参考文献/n/n/n#### C++ 代码/n/ncpp/n#include <iostream>/n#include <algorithm>/n#include <vector>/nusing namespace std;/n/nint n;/nvector<pair<int, int>> students;/n/nbool check(int r) {/n vector<int> idx(n);/n for (int i = 0; i < n; i++) idx[i] = i;/n sort(idx.begin(), idx.end(), [&](int i, int j) { return students[i].first < students[j].first; });/n int sum = 0;/n for (int i = 0; i < n; i++) {/n int id = idx[i];/n sum += students[id].first;/n if (sum - students[id].second >= r) return false;/n }/n return true;/n}/n/nint main() {/n cin >> n;/n students.resize(n);/n for (int i = 0; i < n; i++) {/n cin >> students[i].first >> students[i].second;/n }/n int l = 0, r = 1e6 * n;/n while (l < r) {/n int mid = (l + r) / 2;/n if (check(mid)) r = mid;/n else l = mid + 1;/n }/n cout << l << endl;/n return 0;/n}/n/n/n### 算法2 (暴力枚举) $O(n!n)$/n/n首先，我们可以想到一个 $O(n^2)$ 的做法：枚举排列，计算老师狂暴程度 $r$，并取最小值。/n但是，$n$ 最大为 $1,000$，所以这个算法最多只能得到 $1,000,000$ 分，无法通过本题。/n考虑优化这个算法。如果我们知道了一个排列，如何判断老师狂暴程度是否 $/leq r$ 呢？可以按照答疑时长 $t_i$ 从小到大进行模拟。每当老师答完一个同学的问题时，我们可以更新该同学之后的暴躁程度 $g_i$。如果 $g_i$ 第一次 $/geq r$，我们就可以退出模拟并返回 false（即无法满足 $/min r$ 的条件）。/n问题转化为：如何求出老师狂暴程度 $r$ 是否 $/leq x$。我们可以枚举所有的排列，然后按照上面的方法模拟。如果所有的模拟都成功，说明 $r/leq x$，反之 $r>x$。这种方法的时间复杂度为 $O(n!n/log (10^6n))$，无法通过本题。/n/n#### 时间复杂度/n/n$O(n!n/log (10^6n))$ /n/n#### 参考文献/n/n/n#### C++ 代码/n/ncpp/n#include <iostream>/n#include <algorithm>/n#include <vector>/nusing namespace std;/n/nint n;/nvector<pair<int, int>> students;/n/nbool check(int r, vector<int>& perm) {/n int sum = 0;/n for (int i = 0; i < n; i++) {/n int id = perm[i];/n sum += students[id].first;/n if (sum - students[id].second >= r) return false;/n }/n return true;/n}/n/nint main() {/n cin >> n;/n students.resize(n);/n for (int i = 0; i < n; i++) {/n cin >> students[i].first >> students[i].second;/n }/n vector<int> perm(n);/n for (int i = 0; i < n; i++) perm[i] = i;/n int min_r = 1e6 * n;/n do {/n int r = 0;/n if (check(r, perm)) {/n min_r = min(min_r, r);/n }/n } while (next_permutation(perm.begin(), perm.end()));/n cout << min_r << endl;/n return 0;/n}/n/n